网络异常，图片无法展示
|
题目描述
这是 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 指数是其中最大的那个。
模拟 + 二分
根据题意，我们需要找到满足条件「引用次数至少为 xx 次的 xx 篇论文」中的最大 xx 值。
那么在以最大值 xx 为分割点的正整数数轴上，满足二段性：
- 少于等于 xx 的数值必然满足条件；
- 大于 xx 的数值必然不满足。
因此我们可以通过二分在 [0, n][0,n] 范围内找分割点 xx。
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 复制代码
- 时间复杂度：对 [0, n][0,n] 做二分，复杂度为 O(\log{n})O(logn)；
check函数需要对数组进行线性遍历，复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.274 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
