274 H-Index

Search…

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

179 Largest Number

280 Wiggle Sort

Last modified 2yr ago

Copy link

Contents

274. H-Index

1. Question

2. Implementation

3. Time & Space Complexity

274. H-Index​

1. Question

2. Implementation

3. Time & Space Complexity

274. H-Index