H-Index I & II

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/her N papers 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 with at least3citations each and the remaining two with no more than3citations each, his h-index is3.

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

Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

Follow up: H-Index II

What if thecitationsarray is sorted in ascending order? Could you optimize your algorithm?

Solution I #1:

Sort the arrays first, and then find the last index that satisfied h-index condition.

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

Solution II:

Since the citation array is already sorted, we can just binary search for the largest (last) possible h-index.

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