day123—二分查找—H 指数 II（LeetCode-275）

题目描述

给你一个整数数组citations，其中citations[i]表示研究者的第i篇论文被引用的次数，citations已经按照非降序排列。计算并返回该研究者的 h指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的h指数是指他（她）的 （n篇论文中）至少有h篇论文分别被引用了至少h次。

请你设计并实现对数时间复杂度的算法解决此问题。

示例 1：

输入：citations = [0,1,3,5,6]输出：3解释：给定数组表示研究者总共有 5篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6次。由于研究者有3篇论文每篇至少被引用了 3次，其余两篇论文每篇被引用不多于3次，所以她的h指数是 3 。

示例 2：

输入：citations = [1,2,100]输出：2

提示：

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations按升序排列

解决方案：

算法目标

计算科研人员的H指数：找到一个最大的整数h，使得该科研人员至少有h篇论文的被引用次数至少为h次。

核心思路

1. 排序论文引用次数：便于后续统计

2. 二分查找h值：在[0, n]范围内查找满足条件的最大h

3. 验证条件：统计引用次数≥h的论文数量是否≥h

算法步骤

1. 预处理

sort(citations.begin(), citations.end());

• 对引用次数进行排序

• 虽然排序不是必需的，但能使二分查找更直观

2. 确定查找范围

int left = -1; // 不可行的下界

int right = len + 1; // 可行的上界（开区间）

• h的取值范围：[0, n]（n为论文总数）

• 使用开区间(left, right)，保证left不可行，right可行

3. 二分查找

while(left + 1 < right) { int mid = (left + right) / 2; // 尝试的h值 int ans = 0; // 统计引用次数 ≥ mid 的论文数 for(auto a : citations) { if(a >= mid) ans++; } if(ans >= mid) { left = mid; // mid可行，尝试更大的h } else { right = mid; // mid不可行，尝试更小的h } }

4. 返回结果

return left; // 最大的可行h值

关键点解释

循环不变量

• left：最后一个已知可行的h值

• right：第一个已知不可行的h值

• 区间(left, right)为开区间，其中可能有可行值

判断逻辑

• 如果ans >= mid：有至少mid篇论文被引用至少mid次 → mid可行

• 如果ans < mid：不满足h指数条件 → mid不可行

返回值

• 返回left，即最大的可行h值

• 因为right是第一个不可行的h值，left是最后一个可行的h值

时间复杂度

• 排序：O(n log n)

• 二分查找：O(log n)次迭代

• 每次迭代统计：O(n)

• 总时间：O(n log n)

空间复杂度

• O(1) 或 O(n)（取决于排序算法）

示例

citations = [3,0,6,1,5]
排序后: [0,1,3,5,6]

二分查找过程：
尝试 h=2: 有3篇≥2 → 可行
尝试 h=4: 有2篇≥4 → 不可行
尝试 h=3: 有3篇≥3 → 可行
结果: h=3

算法特点

1. 通用性强：不依赖特殊数据结构

2. 逻辑清晰：直接对应H指数定义

3. 效率适中：适合中等规模数据

4. 易于理解：二分查找框架清晰

函数源码：

class Solution { public: int hIndex(vector<int>& citations) { sort(citations.begin(),citations.end()); int len =citations.size(); int left=0; int right=len+1; while(left+1<right){ int mid=(left+right)/2; int ans=0; for(auto a:citations){ if(a>=mid) ans+=1; } if(ans>=mid) left=mid; else right=mid; } return left; } };