博文中会简要介绍Leetcode P0275题目分析及解题思路。

“H-Index II”是一道中等难度的题目，同时也是p0274的衍生题。这道题其实就是p0274排完序之后利用二分搜索寻找临界点的过程。具体思路不再赘述。

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in an ascending order, return compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index. You must write an algorithm that runs in logarithmic time.

以下是Java的题解代码实现。

class Solution {
    public int hIndex(int[] citations) {
        int N = citations.length, mid = 0, left = 0, right = N-1;
        while (left < right) {
            mid = left+(right-left)/2;
            
            if (N-mid == citations[mid]) {
                return N-mid;
            }
            else if (N-mid > citations[mid]) {
                left = mid+1;
            }
            else {
                right = mid-1;
            }
            
        }
        
        mid = left+(right-left)/2;
        if (N-mid > citations[mid]) {
            return N-mid-1;
        }
        else {
            return N-mid;
        }
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int N = citations.size();
        int left = 0, right = N-1, mid = left+(right-left)/2;
        while (left < right) {
            if (N-mid == citations[mid]) {
                return N-mid;
            }
            else if (N-mid > citations[mid]) {
                left = mid+1;
            }
            else {
                right = mid-1;
            }
            
            mid = left+(right-left)/2;
        }
        
        if (N-mid > citations[mid]) {
            return N-mid-1;
        }
        else {
            return N-mid;
        }
    }
};