274. H-Index
1. Description
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 index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
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, her h-index is 3.
3. Note
- If there are several possible values for h, the maximum one is taken as the h-index.
4. Solutions
Binary Search
n = citations.size()
Time complexity: O(logn)
Space complexity: O(1)
class Solution {
public:
int hIndex(const vector<int> &citations) {
int hindex = 0;
for (int left = 0, right = citations.size(); left <= right;) {
int middle = (left + right) / 2;
if (_is_match(citations, middle)) {
left = middle + 1;
hindex = middle;
} else {
right = middle - 1;
}
}
return hindex;
}
private:
bool _is_match(const vector<int> &citations, const int hindex) {
int count = 0;
for (int cite : citations) {
if (cite >= hindex) {
++count;
}
}
return count >= hindex;
}
};
Bucket Sort
n = citations.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int hIndex(const vector<int> &citations) {
vector<int> cite_count(citations.size() + 1);
for (unsigned long cite : citations) {
++cite_count[min(citations.size(), cite)];
}
for (int i = citations.size(), sum = 0; i > 0; --i) {
sum += cite_count[i];
if (sum >= i) {
return i;
}
}
return 0;
}
};