题目:
给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数,citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (n 篇论文中)总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。
提示:如果 h 有多种可能的值,h 指数 是其中最大的那个。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1:
输入:citations = [0,1,3,5,6]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3 。
示例 2:
输入:citations = [1,2,100]
输出:2
提示:
- n == citations.length
- 1 <= n <= 105
- 0 <= citations[i] <= 1000
- citations 按 升序排列
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/h-index-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
【二分查找】
上一个H指数都没明白题目意思,今天再次看到这个题熟悉又陌生,感谢:@【liweiwei1419】https://leetcode.cn/problems/h-index-ii/solution/jian-er-zhi-zhi-er-fen-cha-zhao-by-liweiwei1419-2/,(这个老师的二分查找讲的特别好!强烈推荐)
这里最主要的问题是要理解到:H指数的含义
题目给的含义是:
- n篇论文中总共有h篇论文分别被引用了至少h次;
- 其余的n-h篇论文每篇被引用的次数不超过h次。
例如:h = 20,表示引用次数大于等于20 的论文数量最少是20篇。
h指数指的是 论文数量,不是引用次数!!!
进一步理解题意:
一个人的论文被引用的次数有一个分水岭(就是h),如果引用次数大于等于h,就代表高引用的论文。所以需要将所给数组进行分割,条件是:分割线右边的引用次数 >= 分割线右边的论文篇数
又因为引用次数的有序排列的,故想到使用二分查找:
- left = 0, right = n - 1, mid = left + (right - left) / 2,循环条件是:left < right;
- 如果nums[mid] < n - mid:表示分割右边的最少引用次数小于右边的论文篇数,说明分割线需要往右移动,下一轮搜索区间应该为[mid+1, right]即left = mid +1
- 例如[0,2,3,|5,8,10,13,16,20],猜测有6篇论文最小引用次数为6,但是最小引用次数才5,所以分割处需要向右移动,[0,2,3,5,|8,10,13,16,20],猜测有5篇论文最小引用次数为8,其余的4篇论文被引用的次数不超过8次。此时mid就是答案为5。
- 上面的对立面:如果nums[mid] >= n - mid:表示分割右边的最少引用次数大于等于右边的论文篇数,下一轮搜索区间应该为[left, mid]即right = mid ;
- 退出循环条件:left == right,返回截止left的论文篇数,需要n - left。
- right = n -1:分割线最右只能在n-1的左边。
- 特殊处理:citations[n-1] == 0,表示如果全部文章的引用次数都为0,则 h 指数就为0。
java代码(left < right):
1 class Solution { 2 public int hIndex(int[] citations) { 3 int n = citations.length; 4 if (citations[n-1] == 0) return 0; 5 int left = 0, right = n - 1; 6 while (left < right){ 7 int mid = left + (right - left) / 2; 8 //如果论文的数量小于中间引用数, 搜索区间往左走 9 //n - mid:分割处右边的论文数量 10 if (citations[mid] < n - mid){ 11 left = mid + 1; 12 }else{ 13 right = mid; 14 } 15 } 16 return n - left; 17 } 18 }
python3代码(left <= right):
1 class Solution: 2 def hIndex(self, citations: List[int]) -> int: 3 n = len(citations) 4 left, right = 0, n - 1 5 if citations[n-1] == 0: 6 return 0 7 while left <= right: 8 mid = left + (right - left) // 2 9 if citations[mid] == n - mid: 10 return citations[mid] 11 elif citations[mid] < n - mid: 12 left = mid + 1 13 else: 14 right = mid - 1 15 # [1,3,5,7,10,13] len-left=4 16 return n - left