274. H-Index.md

274. H-Index

思路

这道题让我们求H指数，如果一个人的学术文章有n篇至少被引用了n次，那么H指数就是满足条件的最大的n。

思路一

根据定义我们可以很好想到先将引用量数组从大到小排个序, 再从后往前遍历直到i >= citations[i]成立, 此时i就是H指数.

思路二

完整的排序复杂度是O(nlogn), 但其实我们没必要排序, 只需要用快排partition的思想不断划分, 例如我们按照从小到大的顺序划分, 若某次划分点索引为k:

• 若 n - k == citations[k], 说明有citations[k]个论文引用量大于等于citations[k], 返回citations[k]即可.
• 否则若n - k > citations[k], 说明结果在右边;
• 否则, 说明结果是citations[k]或左边.

注意边界条件.

C++

思路一

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if (!n) return 0;
        sort(citations.begin(), citations.end(), greater<int>());
        int i = 0;
        for (; i < n; i++) 
            if(i >= citations[i]) break;

        return i;
    }
};

思路二

class Solution {
private:
    // 标准的快排划分(非常重要)
    int partition(vector<int> &arr, int left, int right){
        int pivot = arr[left];
        while(left < right){
            while(left < right && pivot <= arr[right]) right--;
            arr[left] = arr[right]; 
            while(left < right && pivot >= arr[left]) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if(!n) return 0;
        int left = 0, right = n - 1;
        while(left < right){
            int k = partition(citations, left, right);
            if(n - k == citations[k]) return citations[k];
            if(n - k > citations[k]) left = k + 1;
            else right = k;
        }
        return min(citations[left], n - left); // left == right
    }
};