题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，根据内容可以计算一个数字 h，即其中至少有 h 个元素的值大于 h，求 h 的最大值。

思路分享

  • 二分答案的基本思路可看【Leetcode Daily】1283使结果不超过阈值的最小除数。

  • 与之前的求最小不同，现在是求最大，所以二分的写法略有区别。

  • 之前的循环不变量是 left 始终不满足条件， right 始终满足条件（开区间写法），所以当满足条件时是收缩 right；现在则是 left 满足条件， right 不满足，因此不断增大 left 来逼近最大值。

代码解答（强烈建议自行解答后再看）

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

        return left