题目地址

275. H 指数 II

解题思路

题目概述：

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

提示：如果 h 有多种可能的值，h 指数 是其中最大的那个。

请你设计并实现对数时间复杂度的算法解决此问题。

根据题意可以抓住两个关键点，citations 已经按照 升序排列和h 指数的定义。看到数组是有序的，自然就应该想到用二分搜索，接下来就看这个h指数，能否根据h指数的定义写出对应的判断条件来缩小二分搜索可能的取值区间。

步骤一

根据二分搜索的代码模板，写出大致代码框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        # left和right的初始值
        left = 0 
        right = n - 1
        # 用<=符号，是因为搜索区间为[0, n-1]
        while left <= right:
            mid = (right - left) // 2 + left
            if 区间变为[left, mid-1]的条件:
                right = mid - 1
            else:
                left = mid + 1
        return left # 这里对吗？

步骤二

根据h指数的定义，确定搜索区间缩小的条件。原题里面的定义比较绕，咱们可以简单理解下，其实h指数就是全部的n篇论文中，有h篇被引用次数大于等于h，有n-h篇被引用次数小于等于h。

可以假设当前文章下标为mid，则citations[mid]为当前文章被引用次数，此时有n-mid篇文章被引用次数大于citations[mid]，此时会有三种情况：

  1. citations[mid]引用次数大于n-mid篇至少被引用citations[mid]次的文章，说明目标值在mid的左边，此时新的right=mid-1，得到新的搜索区间为[left, mid-1]
  2. citations[mid]引用次数小于n-mid篇至少被引用citations[mid]次的文章，说明目标值在mid的右边，此时新的left=mid+1，得到新的搜索区间为[mid+1, right]
  3. citations[mid]引用次数等于n-mid篇至少被引用citations[mid]次的文章，但是要求h值尽量大，说明目标值可能在mid的左边，此时新的left=mid+1，得到新的搜索区间为[mid+1, right]

还有一点需要注意，题目要求的是求出h的值，所以步骤一中返回left是错误的，应该返回mid-left，所以最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left = 0 
        right = n - 1
        while left <= right:
            mid = (right + left) // 2
            if citations[mid] >= n - mid:
                right = mid - 1
            else:
                left = mid + 1
        return n-left