【二分查找】力扣 275. H 指数 II

一、题目

二、思路

• h 指数是高引用引用次数，而 citations 数组中存储的就是不同论文被引用的次数，并且是按照升序排列的。也就是说 h 指数将整个 citations 数组分成了两部分，左半部分是不够引用 h 次 的论文，右半部分论文的引用次数都是大于等于 h 的。
• 因此，可以采用二分查找的思路来进行求解 h 指数。
• 需要注意的是：有时论文的引用次数并不一定是 citations 数组中的数值。
  • 例如：citations = [0, 1, 2, 4, 5, 6]，其 h 指数是 3。

三、题解

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;
        int ans = Math.min(1, citations[0]);// citations[0] 是引用次数最少的论文
        while (left <= right) {
            int mid = left + (right - left)/2;
            // n - mid 代表右半部分的数组，为符合条件的论文数量
            // 比较 符合条件的论文数量 和 citations[mid]
            // h 指数（ans）更新为二者中较小的
            if (n - mid > citations[mid]) {
                ans = Math.max(ans, citations[mid]);
                left = mid + 1;
            } else if (n - mid < citations[mid]) {
                ans = Math.max(ans, n - mid);
                right = mid - 1;
            } else {
                ans = citations[mid];
                break;
            }
        }
        return ans;
    }
}