LeetCode 275. H指数 II-Python-虚拟区间二分
原题链接
简单
作者:
shiqumi
,
2020-02-18 22:10:43
,
所有人可见
,
阅读 623
虚拟区间二分
- 要二分的区间又是抽象的[0,n]值域区间,而不是给定的引用数字区间
- 首先确定h的值域为0-n,所以l = 0, r =len(nums)
- 规律是只要h满足,那么h-1也满足条件,
- 所以我们要往高处找h,当发现当前值h已经满足,我们要在h右边继续寻找临界点,寻找是否有更大的h
class Solution:
def hIndex(self, citations: List[int]) -> int:
l = 0; r = len(citations) # 注意l,r取值范围与二分区间的关系,二分区间不一定是给定的数组哦
while l < r:
mid = l + r + 1 >> 1
if citations[len(citations) - mid] >= mid: # 查看倒数第mid个数是否大于等于mid
l = mid # 如果大于等于,根据规律说明临界点在右边,也就是要把引用次数增加,符合条件的论文个数减少
else:
r = mid - 1
return r