# 274 H-Index

## 274. [H-Index](https://leetcode.com/problems/h-index/description/)

## 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](https://en.wikipedia.org/wiki/H-index): "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, 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.

## 2. Implementation

**(1) Sort**

```java
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**

```java
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)