Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
According to the : 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.
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
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
Counting Sort
time: O(maxNum), the max cited num
Space: O(n), n is the max cited num
/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function(citations) {
const counts = [];
for (let i = 0; i < citations.length; i++) {
const curr = citations[i];
counts[curr] = counts[curr] ?? 0;
counts[curr] += 1;
}
const sum = [];
sum[counts.length - 1] = counts[counts.length - 1] ?? 0;
for (let i = counts.length - 1; i >= 1; i--) {
const prev = counts[i - 1] ?? 0;
// console.log(sum[i], prev);
sum[i - 1] = sum[i] + prev;
}
for (let i = counts.length; i >= 0; i--) {
const currSum = sum[i];
if (currSum >= i) return i;
}
return 0;
};
Bucket Sort
time: O(N), N is the number of paper
space: O(1)
public int hIndex(int[] citations) {
int n = citations.length;
int[] buckets = new int[n+1];
for(int c : citations) {
if(c >= n) {
buckets[n]++; // genius
} else {
buckets[c]++;
}
}
int count = 0;
for(int i = n; i >= 0; i--) {
count += buckets[i];
if(count >= i) {
return i;
}
}
return 0;
}