Day68 | 灵神 | 二分查找：H指数II

275.H指数II

275. H 指数 II - 力扣（LeetCode）

思路：

很遗憾笔者这道题没做出来，看了灵神的还是不太懂，后来看了评论区各位大佬的解释，来这里浅显的说一下自己的理解

在此之前请先看看灵神的题解，如果看懂了还是不要继续往下看了，如果没看懂的话，我来说一说我疑惑的点，看看是不是也是你疑惑的点呢？

灵神题解：275. H 指数 II - 力扣（LeetCode）

可能对灵神的题解中的疑惑的点

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)

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

2.比较重要的理解，为啥最后返回的是l-1不是l

image-20250320092859009

首先要理解这个，这个比较容易，大家自行理解就好

其次要知道，二分区间[l,r)内的性质我们还没有判断，就是我们不知道二分区间内的数是否满足条件，而二分区间外面的数字是已经被筛选过的，肯定满足条件的

就像是[1,2,3,4,5,6)当我们二分区间为[3,4,5,6)的时候，我们肯定可以判断1,2是合法或者不合法的才会更新到[3,4,5,6)这个区间

再次，通过上面的第一条我们得知citations是来辅助我们筛选h的，所以更新区间时的mid其实就是满足条件的答案h，下面的代码我也有写，用res记录答案，每次更新时res=mid，然后才是l=mid+1

也就是说，我们每次判断的时候l-1==mid，也就是l-1就是答案，这也是为什么灵神最后返回的是l-1

满足条件在灵神的题解中等价于是询问的结果是 “是”

3.citations[citations.size()-mid]>=mid这个判断条件该如何理解？

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

image-20250320094417918

下面的[0,1,2,3,4,5]可以看做我们的h数组，我们正在用二分筛选这个数组，现在筛选的是h==2==mid

citations[0,1,3,5,6]中，citations.size()-mid=5-2=3

citations[3]=5,5>2,而5又是倒数第二个数，5,6，都大于2，那说明肯定至少有两篇论文大于等于2，那么h==2==mid就是一个合法的状态，然后下次更新就是更新到l==mid+1，因为[mid+1,r)这个区间还没有判断是否合法，而[0,mid]这个区间已经被判断为是合法的了

那自然我们确定的答案就是l-1，即mid，就是我们目前帅选出来的最大的h指数了

往后就是反复这个过程

完整代码：

完整代码部分我觉得加一个res比较好理解，也是看的评论区学习到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lower_bound(vector<int>& citations)
    {
        int l=1,r=citations.size()+1;
        int res=0;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(citations[citations.size()-mid]>=mid)
            {
                res=mid;
                l=mid+1;
            }
            else
                r=mid;
        }
        return res;
    }
    int hIndex(vector<int>& citations) {
        return lower_bound(citations);
    }
};