274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/herNpapers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, givencitations = [3, 0, 6, 1, 5], which means the researcher has5papers in total and each of them had received3, 0, 6, 1, 5citations respectively. Since the researcher has3papers withat least3citations each and the remaining two withno more than3citations each, his h-index is3.

Note: If there are several possible values forh, the maximum one is taken as the h-index.

S1: sort O(nlogn)

S2: count sort O(n) trick

对大小为n的数组H index最多为n，所以对于大于n的值可以当做n处理。用大小为n + 1的count数组存储每个值出现的次数，大于或等于n的值存储在count[n] （index即为原数组的值）。

从后往前计算出现值的次数之和sum，到第k个数时sum表示“至少有sum个数有至少k个citations“，第一个满足 k <= sum的k即为所求h index

    int hIndex(vector<int>& citations) {
        int n = citations.size();
        vector<int> count(n + 1, 0);
        for (int i : citations) {
            if (i >= n) {
                count[n]++;  //对大于n的数当作n处理
            }
            else {
                count[i]++;
            }
        }
        for (int k = n, sum = 0; k >= 0; --k) {
            sum += count[k];
            if (k <= sum) {
                return k;
            }
        }
    }

275. H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
S: binary search O(logn)

最后的结果在citation[left], citation[right], n-left, n-right中取

    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if (n == 0) {
            return 0;
        }
        int left = 0, right = n - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            if (citations[mid] <= n - mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        int result = min(n - right, citations[right]);
        result = max(result, min(n - left, citations[left]));
        return result;
    }