274. H-Index

2020, Oct 28 2 mins read

1. Description

Given an array of integers citations where citations[i] is the number of citations a researcher received for their $i^{th}$ paper, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

2. Example

Example 1

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] 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, their h-index is 3.

Example 2

Input: citations = [1,3,1]
Output: 1

3. Constraints

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

4. Solutions

Hash Table

n = citations.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int hIndex(vector<int> &citations) {
        const int n = citations.size();
        unordered_map<int, int> citation_count;
        for (int citation : citations) {
            ++citation_count[min(citation, n)];
        }

        for (int i = n, sum = 0; i > 0; --i) {
            sum += citation_count[i];
            if (sum >= i) {
                return i;
            }
        }

        return 1;
    }
};

Binary Search

n = citations.size()
Time complexity: O(nlogn)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int hIndex(vector<int> citations) {
        const int n = citations.size();
        sort(citations.begin(), citations.end(), [](int a, int b) { return a > b; });

        int left = 0, right = n;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (citations[middle] >= middle + 1) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        return left;
    }
};