274. H 指数
题目描述
输入一个整数数组 citations，citations[i] 是某位研究者第 i 篇论文被引用的次数。
H 指数的定义：若存在 h，使得这位研究者至少有 h 篇论文，每篇都被引用了不少于 h 次，那么 h 就是一个可行值。所有可行值中最大的那个就是 H 指数。
计算并返回这位研究者的 H 指数。
输入：citations = [3,0,6,1,5] 输出：3
解释：一共 5 篇论文，有 3 篇的引用数不少于 3（6、5、3），但找不到 4 篇引用数都不少于 4 的论文，所以答案是 3。
输入：citations = [1,3,1] 输出：1
解释：至少被引用 1 次的论文有 3 篇，但被引用不少于 2 次的只有 1 篇，答案是 1。
数据范围
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
解题思路：排序
把引用次数从大到小排序。排序后第 i 篇（从 0 开始）是引用第 i+1 多的论文：如果它的引用数 c >= i+1，说明前 i+1 篇每篇都至少被引 i+1 次，h 至少是 i+1。一旦某篇 c < i+1，后面的论文引用只会更少、需要的门槛只会更高，不可能再满足，直接停止。
为什么正确
处理到下标 i 时，h = i 表示前 i 篇论文每篇引用都 >= i，即 h 指数至少为 i。
复杂度分析
时间 O(n log n)（排序），空间 O(1) 或排序所需的 O(log n)。
易错点
比较的是 c >= i+1，不是 c >= i；全部论文都满足时 h 等于论文总数 n，不会超过 n；若升序排序，要用 n-i 而不是 i+1 作为门槛。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations.sort(reverse=True)
h = 0
for i, c in enumerate(citations):
if c >= i + 1:
h = i + 1
else:
break
return hclass Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int n = citations.length;
int h = 0;
for (int i = 0; i < n; i++) {
int c = citations[n - 1 - i];
if (c >= i + 1) {
h = i + 1;
} else {
break;
}
}
return h;
}
}class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.rbegin(), citations.rend());
int h = 0;
for (int i = 0; i < (int)citations.size(); i++) {
int c = citations[i];
if (c >= i + 1) {
h = i + 1;
} else {
break;
}
}
return h;
}
};func hIndex(citations []int) int {
sort.Sort(sort.Reverse(sort.IntSlice(citations)))
h := 0
for i, c := range citations {
if c >= i+1 {
h = i + 1
} else {
break
}
}
return h
}var hIndex = function(citations) {
citations.sort((a, b) => b - a);
let h = 0;
for (let i = 0; i < citations.length; i++) {
const c = citations[i];
if (c >= i + 1) {
h = i + 1;
} else {
break;
}
}
return h;
};function hIndex(citations: number[]): number {
citations.sort((a, b) => b - a);
let h = 0;
for (let i = 0; i < citations.length; i++) {
const c = citations[i];
if (c >= i + 1) {
h = i + 1;
} else {
break;
}
}
return h;
}其他解法
排序后从大到小扫一遍就能找到 h，耗时主要在排序；计数排序利用 h ≤ n 把值域压到 [0, n]，线性时间完成。
解法 2：计数排序 时间 O(n)，空间 O(n)
H 指数不会超过论文数 n，所以引用次数大于 n 的都按 n 计。用 cnt[c] 统计引用次数为 c 的论文数。h 从 n 往下枚举，累加 cnt[h] 得到引用次数至少为 h 的论文数，第一次累计值 ≥ h 时 h 就是答案。
利用答案上界为 n，把排序降到线性。需要 O(n) 的计数数组，也要想到“超过 n 的引用次数可以截断”。
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
cnt = [0] * (n + 1)
for c in citations:
cnt[min(c, n)] += 1
total = 0
for h in range(n, -1, -1):
total += cnt[h]
if total >= h:
return h
return 0class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] cnt = new int[n + 1];
for (int c : citations) cnt[Math.min(c, n)]++;
int total = 0;
for (int h = n; h >= 0; h--) {
total += cnt[h];
if (total >= h) return h;
}
return 0;
}
}class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
vector<int> cnt(n + 1);
for (int c : citations) cnt[min(c, n)]++;
int total = 0;
for (int h = n; h >= 0; h--) {
total += cnt[h];
if (total >= h) return h;
}
return 0;
}
};func hIndex(citations []int) int {
n := len(citations)
cnt := make([]int, n+1)
for _, c := range citations {
cnt[min(c, n)]++
}
total := 0
for h := n; h >= 0; h-- {
total += cnt[h]
if total >= h {
return h
}
}
return 0
}var hIndex = function(citations) {
const n = citations.length;
const cnt = new Array(n + 1).fill(0);
for (const c of citations) cnt[Math.min(c, n)]++;
let total = 0;
for (let h = n; h >= 0; h--) {
total += cnt[h];
if (total >= h) return h;
}
return 0;
};function hIndex(citations: number[]): number {
const n = citations.length;
const cnt: number[] = new Array(n + 1).fill(0);
for (const c of citations) cnt[Math.min(c, n)]++;
let total = 0;
for (let h = n; h >= 0; h--) {
total += cnt[h];
if (total >= h) return h;
}
return 0;
}