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, 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
1
class Solution {
2
public int hIndex(int[] citations) {
3
Arrays.sort(citations);
4
5
int n = citations.length;
6
int index = 0;
7
8
while (index < n && citations[n - index - 1] > index) {
9
index++;
10
}
11
return index;
12
}
13
}
Copied!
(2) Count Sort
1
class Solution {
2
public int hIndex(int[] citations) {
3
int n = citations.length;
4
int[] count = new int[n + 1];
5
6
for (int citation : citations) {
7
if (citation >= n) {
8
count[n]++;
9
}
10
else {
11
count[citation]++;
12
}
13
}
14
15
int total = 0;
16
for (int i = n; i >= 0; i--) {
17
total += count[i];
18
if (total >= i) {
19
return i;
20
}
21
}
22
return 0;
23
}
24
}
Copied!

# 3. Time & Space Complexity

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