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.length1 <= n <= 1050 <= citations[i] <= 1000citations按升序排列
解决方案：
算法目标
计算科研人员的H指数：找到一个最大的整数h，使得该科研人员至少有h篇论文的被引用次数至少为h次。
核心思路
排序论文引用次数：便于后续统计
二分查找h值：在[0, n]范围内查找满足条件的最大h
验证条件：统计引用次数≥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
算法特点
通用性强：不依赖特殊数据结构
逻辑清晰：直接对应H指数定义
效率适中：适合中等规模数据
易于理解：二分查找框架清晰
函数源码：
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; } };