275. H-Index II

Given an array of citationssorted in ascending order(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/her N papers have at leasth citations each, and the other N − h papers have no more thanh citations each."

Example:

Input:
citations = [0,1,3,5,6]
Output:
 3 

Explanation: 
[0,1,3,5,6] 
means the researcher has 
5
 papers in total and each of them had 
             received 0
, 1, 3, 5, 6
 citations respectively. 
             Since the researcher has 
3
 papers with 
at least
3
 citations each and the remaining 
             two with 
no more than
3
 citations each, her h-index is 
3
.

Note:

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

Follow up:

  • This is a follow up problem to H-Index , where citations is now guaranteed to be sorted in ascending order.
  • Could you solve it in logarithmic time complexity?
class Solution {
    public int hIndex(int[] citations) {
    int len = citations.length;
    int lo = 0, hi = len - 1;
    while (lo <= hi) {
        int med = (hi + lo) / 2;
        if (citations[med] == len - med) {
            return len - med;
        } else if (citations[med] < len - med) {
            lo = med + 1;
        } else { 
            //(citations[med] > len-med), med qualified as a hIndex,
            // but we have to continue to search for a higher one.
            hi = med - 1;
        }
    }
    return len - lo;
}
}

results for ""

    No results matching ""