题目描述
这是 LeetCode 上的 275. H 指数 II ，难度为 中等。
Tag : 「二分」
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"
示例:
输入: citations = [0,1,3,5,6]输出: 3
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。
说明:
如果 h 有多有种可能的值 ，h 指数是其中最大的那个。
进阶：
- 这是 H 指数 的延伸题目，本题中的 citations 数组是保证有序的。
- 你可以优化你的算法到对数时间复杂度吗？
基本分析
本题与 274. H 指数 的主要不同有两方面：
显然，增加了数组有序特性，扩大了数据范围。可以猜到利用此特性，存在时间复杂度更低的算法实现。
二分答案（线性 check）
在 (题解) 274. H 指数 中，我们使用了 的二分做法，算法的主要瓶颈在于 复杂度的 check。
当然对于 的数据量，使用 复杂度没有任何问题。
Java 代码：
class Solution {public int hIndex(int[] cs) {
int n = cs.length;
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(cs, mid)) l = mid;
else r = mid - 1;
}
return r;
}
boolean check(int[] cs, int mid) {
int ans = 0;
for (int i : cs) if (i >= mid) ans++;
return ans >= mid;
}
}
Python 3 代码：
class Solution:def hIndex(self, citations: List[int]) -> int:
def check(cs, mid):
return sum(i>=mid for i in cs) >= mid
n = len(citations)
l, r = 0, n
while l < r:
mid = l + r + 1 >> 1
if check(citations, mid):
l = mid
else:
r = mid - 1
return r
- 时间复杂度：对做二分，复杂度为；check 函数需要对数组进行线性遍历，复杂度为。整体复杂度为
- 空间复杂度：
二分下标（根据与 关系）
在解法一中，显然我们没有利用本题的「数组有序」的特性。
根据对 H 指数 定义，如果 升序，在最大的符合条件的分割点 的右边（包含分割点），必然满足 ，我们应当对其进行计数，对于分割点的左边，必然不满足 ，无需进行计数。
因此，我们可以利用 分割点右边书的个数与分割点 的大小关系进行二分 。
假设存在真实分割点下标 ，其值大小为 ，分割点右边的数值个数为 ，根据 H 指数 的定义，必然有 关系：
- 在分割点的右边：非严格单调递增，而书的个数严格单调递减，仍然满足关系；
- 在分割点的左边：非严格单调递减，书的个数严格单调递增，作为真实分割点，因此必然不满足关系。
利用此「二段性」进行二分即可，二分出下标后，再计算出书的个数。
Java 代码：
class Solution {public int hIndex(int[] cs) {
int n = cs.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (cs[mid] >= n - mid) r = mid;
else l = mid + 1;
}
return cs[r] >= n - r ? n - r : 0;
}
}
Python 3 代码：
class Solution:def hIndex(self, citations: List[int]) -> int:
n = len(citations)
l, r = 0, n - 1
while l < r:
mid = l + r >> 1
if citations[mid] >= n - mid:
r = mid
else:
l = mid + 1
return n - r if citations[r] >= n - r else 0
- 时间复杂度：
- 空间复杂度：
其他「二分」相关内容
题目
题解
难度
推荐指数
4. 寻找两个正序数组的中位数
LeetCode 题解链接
困难
29. 两数相除
LeetCode 题解链接
中等
33. 搜索旋转排序数组
LeetCode 题解链接
中等
34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 题解链接
中等
35. 搜索插入位置
LeetCode 题解链接
简单
74. 搜索二维矩阵
LeetCode 题解链接
中等
81. 搜索旋转排序数组 II
LeetCode 题解链接
中等
153. 寻找旋转排序数组中的最小值
LeetCode 题解链接
中等
154. 寻找旋转排序数组中的最小值 II
LeetCode 题解链接
困难
220. 存在重复元素 III
LeetCode 题解链接
中等
274. H 指数
LeetCode 题解链接
中等
278. 第一个错误的版本
LeetCode 题解链接
简单
354. 俄罗斯套娃信封问题
LeetCode 题解链接
困难
363. 矩形区域不超过 K 的最大数值和
LeetCode 题解链接
困难
374. 猜数字大小
LeetCode 题解链接
简单
778. 水位上升的泳池中游泳
LeetCode 题解链接
困难
852. 山脉数组的峰顶索引
LeetCode 题解链接
简单
981. 基于时间的键值存储
LeetCode 题解链接
中等
1004. 最大连续1的个数 III
LeetCode 题解链接
中等
1011. 在 D 天内送达包裹的能力
LeetCode 题解链接
中等
1208. 尽可能使字符串相等
LeetCode 题解链接
中等
1438. 绝对差不超过限制的最长连续子数组
LeetCode 题解链接
中等
1482. 制作 m 束花所需的最少天数
LeetCode 题解链接
中等
1707. 与数组中元素的最大异或值
LeetCode 题解链接
困难
1751. 最多可以参加的会议数目 II
LeetCode 题解链接
困难
最后
这是我们「刷穿 LeetCode」系列文章的第 No.275 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
【转自：武汉网站制作 http://www.wh5w.com提供，感恩】