https://leetcode.com/problems/h-index/description/
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 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.
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
- code
class Solution {
public int hIndex(int[] citations) {
int l = Arrays.stream(citations).min().getAsInt();
int r = Arrays.stream(citations).max().getAsInt();
while (l < r){
int m = (l + r) / 2;
if (hSuccess(citations, m)){
l = m + 1;
}else{
r = m;
}
}
if (hSuccess(citations, l)) return Math.min(l, citations.length);
return Math.min(l-1, citations.length);
}
public boolean hSuccess(int[] arr, int h){
return Arrays.stream(arr).filter(i -> i >= h).count() >= h;
}
}
- code #countingSort
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int count[] = new int[n + 1];
for (int c: citations){
count[Math.min(c, n)]++;
}
int h = n;
int sumAtLeastH = count[n];
while(h > sumAtLeastH){
h--;
sumAtLeastH += count[h];
}
return h;
}
}