# 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 the[definition of h-index on Wikipedia](https://en.wikipedia.org/wiki/H-index): "A scientist has indexhifhof his/herNpapers have**at least**hcitations each, and the otherN − hpapers have**no more than**hcitations each."
>
> For example, given`citations = [3, 0, 6, 1, 5]`, which means the researcher has`5`papers in total and each of them had received`3, 0, 6, 1, 5`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, his h-index is`3`.
>
> **Note**: If there are several possible values for`h`, 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).