274 H-Index

274. H-Index

1. Question

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 indexhifhof his/herNpapers have at least h citations each, and the otherN − h papers have no more than hcitations 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.

2. Implementation

(1) Sort

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);

        int n = citations.length;
        int index = 0;

        while (index < n && citations[n - index - 1] > index) {
            index++;
        }
        return index;
    }
}

(2) Count Sort

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1];

        for (int citation : citations) {
            if (citation >= n) {
                count[n]++;
            }
            else {
                count[citation]++;
            }
        }

        int total = 0;
        for (int i = n; i >= 0; i--) {
            total += count[i];
            if (total >= i) {
                return i;
            }
        }
        return 0;
    }
}

3. Time & Space Complexity

Sort: 时间复杂度O(nlogn), 空间复杂度O(1)

Count Sort: 时间复杂度O(n), 空间复杂度O(n)