H-Index

https://leetcode.com/problems/h-index/description/

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 thedefinition of h-index on Wikipedia: "A scientist has indexhifhof his/herNpapers haveat leasthcitations each, and the otherN − hpapers haveno more thanhcitations 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 withat least3citations each and the remaining two withno more than3citations each, his h-index is3.

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

Thoughts

brute-force: i从1遍历到N, 对i数每篇paper引用是否达到i. O(N^2)

还可以想到先排序, 变成[0, 1, 3, 6, 5] 那么len - i即 达到nums[i] 的paper数目, 则h-index = min(len - i, nums[i]). O(nlgn)

看到别人的还有O(n)的算法。利用的是类似counting sort的思想。根据h-index定义我们知道h-index最多为N， 我们分别把引用为0~N的频率统计出来，当引用大于N时也放入N中。然后我们从后往前数，那么引用大于等于N的论文数目即N对应的频率，引用大于N-1的论文数目即freq(N) + freq(N - 1), 当当前的累加freq >= i时，即所求。

Code

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] freq = new int[n + 1];
        for (int c : citations) {
            if (c >= n) {
                freq[n]++;
            } else {
                freq[c]++;
            }
        }

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

        return 0;
    }
}

Analysis

时空复杂度都是O(n).