274. H-Index
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)
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)
class Solution {
public:
int hIndex(const vector<int> &citations) {
const int n = citations.size();
int left = 0, right = n; // [left, right]
while (left <= right) {
int middle = left + ((right - left) >> 1);
int count = std::count_if(
citations.begin(), citations.end(), [middle](int x) { return x >= middle; });
if (count >= middle) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return right;
}
};