LeetCode 275. H 指数 II

约 4 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
数组 二分查找

题目描述

✅ 275. H 指数 II

image-20260928231145156

image-20260928231145157

题意分析

数组已按引用次数从小到大排列。H 指数是满足“至少有 h 篇论文，每篇至少被引用 h 次”的最大整数 h，取值在 0..n 内。要求利用已有顺序，在对数时间内求出答案。

解法：二分查找判定答案

核心思路

[!blue]

若要判断某个 h 是否可行，只需看引用次数最高的 h 篇论文：连它们中引用最少的一篇都达到 h，这 h 篇就全部达标；若它也不足，其他论文更不可能补足数量。

把这组论文写成从下标 i 开始的后缀，篇数就是 h = n - i，条件变为 citations[i] >= n - i。随着 i 右移，引用次数不减，要求的篇数却递减，因此条件一定先假后真。找到第一个满足的位置，就得到篇数最多的可行后缀。

使用闭区间 [left, right] 二分。若中点引用次数不足 n - mid，更左位置的引用不会更多、要求篇数却更多，所以整个左半都不满足，令 left = mid + 1。若引用次数超过要求，中点已经满足，但更左侧可能对应更大 H 指数，继续令 right = mid - 1。

若恰好相等，可以直接返回 n - mid：中点满足，而任意更左位置的引用最多为这个值，所要求的篇数却严格更多，所以它们都不满足。没有提前返回时，循环结束的 left 就是首个满足位置，答案为 n - left；若所有位置都不满足，left = n，自然得到 0。

解题步骤

  1. 初始化 left = 0、right = n - 1。
  2. 当 left <= right 时，取中点 mid，计算后缀篇数 h = n - mid。
  3. 若 citations[mid] == h，返回 h；若引用更少，移动左边界；若引用更多，移动右边界。
  4. 循环结束后返回 n - left。

代码实现

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int h = n - mid;

            // 等号时更左侧要求更多论文、引用却不更多，可直接确定答案
            if (citations[mid] == h) {
                return h;
            } else if (citations[mid] < h) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 左边界是首个满足位置，长度减边界才是论文数量
        return n - left;
    }
}

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n-1

    for left <= right {
        mid := left + (right-left)/2
        h := n - mid
        // 等号时更左侧要求更多论文、引用却不更多，可直接确定答案
        if citations[mid] == h {
            return h
        } else if citations[mid] < h {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    // 左边界是首个满足位置，长度减边界才是论文数量
    return n - left
}

复杂度分析

  • 时间复杂度：$O(\log(n+1))$，每轮排除约一半位置。
  • 空间复杂度：$O(1)$，几个二分变量。

关键点总结

[!green]

  • 答案是符合条件的后缀数量，不是边界下标或引用值。
  • 首个满足位置可能是 0，也可能不存在；对应答案分别为 n 和 0。
  • 等号提前返回依赖“引用不减、所需篇数严格递减”，不是一般二分边界都能使用的规则。

易错点总结

[!yellow]

  • 直接返回边界下标，会把位置当 H 指数。
  • 全假时返回长度减右边界，会多一。
  • 已经有序仍再次排序，会抵消对数查询的优势。

相似题目

题目 难度 关联与区别
274. H 指数 中等 本题利用输入升序，把h指数判定转成单调边界查询，避免再次排序。
35. 搜索插入位置 简单 同样找第一个满足条件的下标，本题条件为当前位置引用数至少覆盖其右侧论文数量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/27815780
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！