【每日算法】利用二段性找最大 H 指数

【每日算法】利用二段性找最大 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 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。