274. H-Index 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int hIndex(int[] citations) {
        // citations[i] 表示第 i 篇论文被引用的次数
        // [3, 0, 6, 1, 5]

        int left = 0, right = citations.length; // [left, right]

        int res = 0;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int count = 0;
            for (int c : citations) {
                if (c >= mid) {
                    count++;
                }
            }

            if (count >= mid) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }
}

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int hIndex(int[] citations) {
        // citations[i] 表示第 i 篇论文被引用的次数
        // [3, 0, 6, 1, 5]

        int left = 0, right = citations.length; // [left, right]

        while (left <= right) {
            int mid = (left + right) >>> 1;
            int count = 0;
            for (int c : citations) {
                if (c >= mid) {
                    count++;
                }
            }

            if (count >= mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right; // 当最后一次循环 left 与 right 相等时，如果满足条件则 left 会加 1, 所以应该取 right, 如果不满足条件，则 right 会减 1, 所以也应该取 right
    }
}

References

274. H-Index