题目描述 这是 LeetCode 上的 274. H 指数 ，难度为 中等。 Tag : 「二分」 给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h指数
题目描述
这是 LeetCode 上的 274. H 指数 ，难度为 中等。
Tag : 「二分」
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
示例：
输入：citations = [3,0,6,1,5]输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
提示：如果 h 有多种可能的值，h 指数是其中最大的那个。
模拟 + 二分
根据题意，我们需要找到满足条件「引用次数至少为 次的 篇论文」中的最大 值。
那么在以最大值 为分割点的正整数数轴上，满足二段性：
- 少于等于的数值必然满足条件；
- 大于的数值必然不满足。
因此我们可以通过二分在 范围内找分割点 。
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 函数需要对数组进行线性遍历，复杂度为。整体复杂度为
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.274 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。