LeetCode 第274题：H指数 · 江川个人博客

📖 文章摘要

本文详细解析LeetCode第274题“H指数”，这是一道排序和计数优化的中等问题。文章提供了从基础排序到高效计数排序的多种解法，包含H指数定义的深入理解和算法优化思路，配有详细的数学建模过程和性能分析。适合想要掌握排序优化技巧和数学建模能力的算法学习者。

核心知识点： 排序算法、计数排序、数学建模、H指数定义理解
难度等级： 中等
推荐人群： 排序算法学习者、数学建模爱好者

题目描述

给你一个整数数组 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

提示

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

解题思路

核心分析

H指数定义理解： H指数 = h 意味着：

至少有 h 篇论文被引用了至少 h 次
其余的 (n-h) 篇论文被引用次数不超过 h 次
我们要找的是满足条件的最大的 h 值

关键观察：

将论文按引用次数排序后，对于位置 i 的论文，如果 citations[i] >= n-i，说明从位置 i 开始的所有论文（共 n-i 篇）都至少被引用了 n-i 次
第一个满足条件的位置对应的 n-i 就是答案
H指数最大不会超过论文总数n

优化思路：

利用H指数的范围限制，使用计数排序优化
从可能的最大值开始检查，找到第一个满足条件的H指数

方法一：排序 + 线性扫描

核心思想：

将引用次数数组排序（升序）
从左到右遍历，找到第一个满足 citations[i] >= n-i 的位置
返回 n-i 作为H指数

算法步骤：

对引用次数数组进行排序
遍历排序后的数组
检查每个位置是否满足条件
返回第一个满足条件的H指数

复杂度分析：

时间复杂度：O(n log n)，排序的时间复杂度
空间复杂度：O(1)，原地排序

方法二：计数排序（桶排序）

核心思想：

由于H指数最大不会超过论文总数n，创建大小为n+1的计数数组
统计每个引用次数的论文数量（超过n的都放在第n个桶中）
从后往前累加，找到第一个满足条件的H指数

算法步骤：

创建计数数组，统计引用次数分布
从后往前累加论文数量
检查累加数量是否满足H指数条件
返回第一个满足条件的H指数

复杂度分析：

时间复杂度：O(n)，线性时间复杂度
空间复杂度：O(n)，需要额外的计数数组

方法三：二分查找

核心思想：

H指数的取值范围是[0, n]，具有单调性
对于任意的h值，我们可以O(n)时间内判断是否满足条件
使用二分查找找到最大的满足条件的h值

算法步骤：

设置二分查找的左右边界
对于每个中点值，检查是否满足H指数条件
根据检查结果调整搜索范围
返回最大的满足条件的H指数

复杂度分析：

时间复杂度：O(n log n)，二分查找O(log n)，每次检查O(n)
空间复杂度：O(1)，只使用常数额外空间

图解思路

排序后分析表

以 citations = [3,0,6,1,5] 为例：

步骤	数组状态	当前位置	检查条件	结果	说明
初始	[3,0,6,1,5]	-	-	-	原始数组
排序后	[0,1,3,5,6]	-	-	-	升序排列
位置0	[0,1,3,5,6]	0	0 >= 5?	❌	0 < 5，不满足
位置1	[0,1,3,5,6]	1	1 >= 4?	❌	1 < 4，不满足
位置2	[0,1,3,5,6]	2	3 >= 3?	✅	3 >= 3，满足条件
结果	-	-	-	3	返回 n-2 = 3

计数排序分析表

引用次数	论文数量	累积论文数	H指数检查	结果	说明
≥5	2	2	2 >= 5?	❌	不满足H指数=5
≥4	2	2	2 >= 4?	❌	不满足H指数=4
≥3	3	3	3 >= 3?	✅	满足H指数=3
≥2	3	3	-	-	已找到答案

代码实现

C# 实现

// 方法一：排序 + 线性扫描
public class Solution {
    public int HIndex(int[] citations) {
        Array.Sort(citations);
        int n = citations.Length;
        
        for (int i = 0; i < n; i++) {
            // 从位置i开始有n-i篇论文，如果citations[i] >= n-i
            // 说明这n-i篇论文都至少被引用了n-i次
            if (citations[i] >= n - i) {
                return n - i;
            }
        }
        return 0;
    }
}

// 方法二：计数排序（推荐）
public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int[] count = new int[n + 1];
        
        // 统计每个引用次数的论文数量
        foreach (int citation in citations) {
            if (citation >= n) {
                count[n]++;
            } else {
                count[citation]++;
            }
        }
        
        // 从后向前遍历，找到第一个满足条件的h
        int papers = 0;
        for (int h = n; h >= 0; h--) {
            papers += count[h];
            if (papers >= h) {
                return h;
            }
        }
        
        return 0;
    }
}

// 方法三：二分查找
public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int left = 0, right = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (Check(citations, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
    
    private bool Check(int[] citations, int h) {
        int count = 0;
        foreach (int citation in citations) {
            if (citation >= h) {
                count++;
            }
        }
        return count >= h;
    }
}

Python 实现

# 方法一：排序 + 线性扫描
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        
        for i in range(n):
            if citations[i] >= n - i:
                return n - i
        return 0

# 方法二：计数排序（推荐）
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        buckets = [0] * (n + 1)
        
        # 计数：引用次数为i的论文有buckets[i]篇
        for citation in citations:
            if citation >= n:
                buckets[n] += 1
            else:
                buckets[citation] += 1
        
        count = 0
        # 从后往前检查，count表示引用次数>=i的论文总数
        for i in range(n, -1, -1):
            count += buckets[i]
            if count >= i:
                return i
        return 0

# 方法三：二分查找
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n
        
        while left <= right:
            mid = (left + right) // 2
            if self.check(citations, mid):
                left = mid + 1
            else:
                right = mid - 1
        return right
    
    def check(self, citations, h):
        count = sum(1 for citation in citations if citation >= h)
        return count >= h

C++ 实现

// 方法一：排序 + 线性扫描
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int n = citations.size();
        
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n - i) {
                return n - i;
            }
        }
        return 0;
    }
};

// 方法二：计数排序（推荐）
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        vector<int> buckets(n + 1, 0);
        
        // 计数
        for (int citation : citations) {
            if (citation >= n) {
                buckets[n]++;
            } else {
                buckets[citation]++;
            }
        }
        
        int count = 0;
        // 从后往前检查
        for (int i = n; i >= 0; i--) {
            count += buckets[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }
};

执行结果

C# 实现

排序法：执行用时：88 ms，内存消耗：39.8 MB
计数排序：执行用时：76 ms，内存消耗：40.2 MB
二分查找：执行用时：84 ms，内存消耗：39.6 MB

Python 实现

排序法：执行用时：32 ms，内存消耗：16.2 MB
计数排序：执行用时：28 ms，内存消耗：16.8 MB
二分查找：执行用时：36 ms，内存消耗：16.1 MB

C++ 实现

排序法：执行用时：4 ms，内存消耗：8.6 MB
计数排序：执行用时：0 ms，内存消耗：8.9 MB
二分查找：执行用时：4 ms，内存消耗：8.5 MB

性能对比

语言	方法	执行用时	内存消耗	特点
C++	计数排序	0 ms	8.9 MB	性能最优，线性时间复杂度
Python	计数排序	28 ms	16.8 MB	效率高，内存占用适中
C#	计数排序	76 ms	40.2 MB	性能良好，实现清晰

代码亮点

🎯 计数排序充分利用H指数的范围特性，实现O(n)时间复杂度
💡 排序方法直观易懂，通过数组索引巧妙对应论文数量
🔍 二分查找体现了问题的单调性，提供了另一种思路
🎨 三种方法各有优势，展示了不同的算法思维和权衡

常见错误分析

🚫 边界情况处理：所有论文引用次数都为0时，H指数为0，容易遗漏
🚫 理解定义错误：混淆“至少h篇论文被引用至少h次”的含义
🚫 计数排序边界：超过n的引用次数需要合并到第n个桶中
🚫 排序方向错误：需要升序排序，然后从左到右检查

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
排序 + 扫描	O(n log n)	O(1)	简单直观，易于理解和实现	时间复杂度较高
计数排序	O(n)	O(n)	时间复杂度最优，效率最高	需要额外空间，适用于有限范围
二分查找	O(n log n)	O(1)	体现单调性，思路巧妙	时间复杂度不是最优

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第274题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

核心分析

方法一：排序 + 线性扫描

方法二：计数排序（桶排序）

方法三：二分查找

图解思路

排序后分析表

计数排序分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流