这是 LeetCode 上的「274. H 指数」,难度为「中等」。
Tag : 「二分」、「数学」
给你一个整数数组 citations
,其中 citations[i]
表示研究者的第 i
篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h
指数的定义:h
代表“高引用次数”,一名科研人员的 h指数是指他(她)的 (n
篇论文中)总共有 h
篇论文分别被引用了至少 h
次。且其余的 n - h
篇论文每篇被引用次数 不超过 h
次。
如果 h
有多种可能的值,h
指数是其中最大的那个。
示例 1:
输入:citations = [3,0,6,1,5]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。
示例 2:
输入:citations = [1,3,1]
输出:1
提示:
为了方便,将 citations
记为 cs
。
所谓的 h
指数是指一个具体的数值,该数值为“最大”的满足「至少发表了 x
篇论文,且每篇论文至少被引用 x
次」定义的合法数,重点是“最大”。
用题面的实例
来举个 🌰,给定所有论文的引用次数情况为 cs = [3,0,6,1,5]
,可统计满足定义的数值有哪些:
,含义为「至少发表了
篇,且这
篇论文至少被引用
次」,空集即满足,恒成立;
,含义为「至少发表了
篇,且这
篇论文至少被引用
次」,可以找到这样的组合,如 [3]
,成立;
,含义为「至少发表了
篇,且这
篇论文至少被引用
次」,可以找到这样的组合,如 [3, 6]
,成立;
,含义为「至少发表了
篇,且这
篇论文至少被引用
次」,可以找到这样的组合,如 [3, 6, 5]
,成立;
,含义为「至少发表了
篇,且这
篇论文至少被引用
次」,找不到这样的组合,不成立;
实际上,当遇到第一个无法满足的数时,更大的数值就没必要找了。一个简单的推导:
至少出现
次的论文数不足
篇 => 至少出现
次的论文必然不足
篇 => 至少出现
次的论文必然不足
篇(即更大的
不满足)。
基于此分析,我们发现对于任意的 cs
(论文总数量为该数组长度
),都必然对应了一个最大的 h
值,且小于等于该 h
值的情况均满足,大于该 h
值的均不满足。
那么,在以最大 h
值为分割点的数轴上具有「二段性」,可通过「二分」求解该分割点(答案)。
最后考虑在什么值域范围内进行二分?
一个合格的二分范围,仅需确保答案在此范围内即可。
再回看我们关于 h
的定义「至少发表了 x
篇论文,且每篇论文至少被引用 x
次」,满足条件除了引用次数,还有论文数量,而总的论文数量只有
,因此最大的 h
只能是
本身,而不能是比
大的数,否则论文数量就不够了。
综上,我们只需要在
范围进行二分即可。对于任意二分值 mid
,只需线性扫描 cs
即可知道其是否合法。
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;
}
}
C++ 代码:
class Solution {
public:
int hIndex(vector<int>& cs) {
int n = cs.size();
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(cs, mid)) l = mid;
else r = mid - 1;
}
return r;
}
bool check(vector<int>& cs, int x) {
int cnt = 0;
for (int c : cs) {
if (c >= x) cnt++;
}
return cnt >= x;
}
};
Python 代码:
class Solution:
def hIndex(self, cs: List[int]) -> int:
n = len(cs)
l, r = 0, n
while l < r:
mid = (l + r + 1) // 2
if sum(c >= mid for c in cs) >= mid:
l = mid
else:
r = mid - 1
return r
TypeScript 代码:
function hIndex(cs: number[]): number {
const check = function (cs: number[], x: number): boolean {
let cnt: number = 0;
for (let c of cs) {
if (c >= x) cnt++;
}
return cnt >= x;
}
const n = cs.length;
let l = 0, r = n;
while (l < r) {
const mid = Math.floor((l + r + 1) / 2);
if (check(cs, mid)) l = mid;
else r = mid - 1;
}
return r;
};
做二分,复杂度为
;check
函数需要对数组进行线性遍历,复杂度为
。整体复杂度为
根据分析,利用最大的 h
不超过
,我们可以再进一步,利用空间换时间,将复杂度降低到
。
假设我们预处理出引用次数所对应的论文数量 cnt
,其中 cnt[a] = b
含义为引用次数 「恰好」 为 a
的论文数量有 b
篇。
那么再利用 h
是“最大”的满足定义的合法数,我们从
开始往前找,找到的第一个满足条件的数,即是答案。
具体的,创建 cnt
数组,对 cs
进行计数,由于最大 h
不超过
,因此对于引用次数超过
的论文,可等价为引用次数为
,即有计数逻辑 cnt[min(c, n)]++
。
再根据处理好的 cnt
,从
开始倒序找 h
。
由于我们处理的 cnt[a]
含义为引用次数 「恰好」 为 a
,但题目定义则是 「至少」。同时「至少出现
次」的集合必然慢「至少出现
次」要求(子集关系),我们可以使用变量 tot
,对处理过的 cnt[i]
进行累加,从而实现从 「恰好」 到 「至少」 的转换。
Java 代码:
class Solution {
public int hIndex(int[] cs) {
int n = cs.length;
int[] cnt = new int[n + 10];
for (int c : cs) cnt[Math.min(c, n)]++;
for (int i = n, tot = 0; i >= 0; i--) {
tot += cnt[i];
if (tot >= i) return i;
}
return -1; // never
}
}
C++ 代码:
class Solution {
public:
int hIndex(vector<int>& cs) {
int n = cs.size();
vector<int> cnt(n + 10, 0);
for (int c : cs) cnt[min(c, n)]++;
for (int i = n, tot = 0; i >= 0; i--) {
tot += cnt[i];
if (tot >= i) return i;
}
return -1; // never
}
};
Python 代码:
class Solution:
def hIndex(self, cs: List[int]) -> int:
n = len(cs)
cnt = [0] * (n + 10)
for c in cs:
cnt[min(c, n)] += 1
tot = 0
for i in range(n, -1, -1):
tot += cnt[i]
if tot >= i:
return i
return -1 # never
TypeScript 代码:
function hIndex(cs: number[]): number {
const n = cs.length;
const cnt = new Array(n + 10).fill(0);
for (let c of cs) cnt[Math.min(c, n)]++;
for (let i = n, tot = 0; i >= 0; i--) {
tot += cnt[i];
if (tot >= i) return i;
}
return -1; // never
};
这是我们「刷穿 LeetCode」系列文章的第 No.274
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。