力扣面试150 H 指数 计数数组 模拟题

Problem: 274. H 指数

思路

👨‍🏫 灵神题解

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

Code

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] cnt = new int[n + 1];//cnt[i] 表示 引用数i 的文章的数量
        for (int c : citations) {
            cnt[Math.min(c, n)]++; // 引用次数 > n，等价于引用次数为 n
        }
        int s = 0;// s 记录引用数 >= i 的文章数量
        for (int i = n; ; i--) { // i=0 的时候，s>=i 一定成立
            s += cnt[i];
            if (s >= i) { // 说明有至少 i 篇论文的引用次数至少为 i
                return i;
            }
        }
    }
}