275. H-Index II

26 年 2 月 26 日 星期四
693 字
4 分钟

275. H-Index IIScreenshot 2026-02-26 at 7.32.22 pm

解析:

https://leetcode.cn/problems/h-index-ii/solutions/2504326/tu-jie-yi-tu-zhang-wo-er-fen-da-an-si-ch-d15k

1.理解本道题最重要的一点

为什么左闭右开区间的时候,l要初始化为1,r要初始化为citations.size()+1呢?

因为这道题二分的其实是h指数的数组,而h指数的数组你可以看做是[0,1,2,3,4,5],因为h指数可以取到这些数字,也就是说h指数的范围是[0,5]即[0,citations.size()],但是笔者写的是左开右闭区间所以就是[0,citations.size()+1)了,也就是[0,6)

所以其实我们二分的是[0,1,2,3,4,5]这个数组,我们最后返回的答案一定在这之中

所以说白了citations这个数组起到的作用就是辅助我们把h从[0,citations.size()+1)给挑选出来,也就是用来写判断条件的,除此之外没有什么其他的作用

而为什么l初始化为0而不是1呢?

这个灵神有说

肯定有0篇论文的引用次数>=0,那么二分区间就不需要包括0,直接从1开始就好了,也就是说我们二分的区间其实是[1,2,3,4,5],等价于[1,2,3,4,5,6)

这让我想起洛谷做过的一道题,是砍树的,也是把树的高度进行二分而不是去看树的高度的数组,完了有空再去刷一下

citations.size()-mid 的理解

citations.size()-mid这个下标对应的是数组倒数第mid个数,因为是单调自增的,如果说 这个下标对应的数要大于我们本轮筛选的h即mid,那说明这个数以及以后的数都是大于mid的,即至少有mid篇论文被引用mid次

在答案空间中二分

对于citations = [0,1,3,5,6], length = 5 ,有[0, 1, 2, 3, 4, 5]种情况

在[0, 1, 2, 3, 4, 5]中二分,每个代表的意义如下,每次check这个答案能不能满足要求

Screenshot 2026-02-26 at 7.42.10 pm
js
// /**
//  * @param {number[]} citations
//  * @return {number}
//  */

var hIndex = function (citations) {
  // 在区间 [left, right) 内询问
  const n = citations.length
  let left = 0 // ⚠️可改成1
  let right = n + 1 // ⚠️为什么是n + 1,因为在答案空间中二分
  while (left < right) {
    // 区间不为空
    // 循环不变量:
    // left-1 的回答一定为「是」
    // right 的回答一定为「否」
    const mid = Math.floor((left + right) / 2)
    // 引用次数最多的 mid 篇论文,引用次数均 >= mid
    if (citations[n - mid] >= mid) {
      //⚠️假定mid是答案,如果mid是答案,更新 left - 1 = mid
      left = mid + 1 // 询问范围缩小到 [mid+1, right)
    } else {
      right = mid // 询问范围缩小到 [left, mid)
    }
  }
  // 根据循环不变量,left-1 现在是最大的回答为「是」的数
  return left - 1
}

文章标题:275. H-Index II

文章作者:Sirui Chen

文章链接:https://blog.siruichen.me/posts/275_h-index_ii[复制]

最后修改时间:


商业转载请联系站长获得授权,非商业转载请注明本文出处及文章链接,您可以自由地在任何媒体以任何形式复制和分发作品,也可以修改和创作,但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。