Leetcode.275 H 指数 II
题目链接
Leetcode.275 H 指数 II
mid
题目描述
给你一个整数数组 c i t a t i o n s citations citations ，其中 c i t a t i o n s [ i ] citations[i] citations[i] 表示研究者的第 i i i 篇论文被引用的次数， c i t a t i o n s citations citations 已经按照 升序排列 。计算并返回该研究者的 h h h 指数。
h h h 指数的定义： h h h 代表“高引用次数”（ h i g h c i t a t i o n s high citations highcitations），一名科研人员的 h h h 指数是指他（她）的 （ n n n 篇论文中）总共有 h h h 篇论文分别被引用了至少 h 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 = c i t a t i o n s . l e n g t h n = citations.length n=citations.length
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
- 0 ≤ c i t a t i o n s [ i ] ≤ 1000 0 \leq citations[i] \leq 1000 0≤citations[i]≤1000
- c i t a t i o n s citations citations 按 升序排列
解法：二分
初始 l = 0 , r = n l = 0 , r = n l=0,r=n；
我们可以得到 m i d mid mid ，如果 c i t a t i o n s citations citations 中 大于等于 m i d mid mid 的元素一共有 c n t cnt cnt 个。
- 如果 c n t ≥ m i d cnt \geq mid cnt≥mid，说明 c n t cnt cnt 指数，是满足 c i t a t i o n s citations citations 的，故 l = m i d l = mid l=mid；
- 如果 c n t ≥ m i d cnt \geq mid cnt≥mid，说明 c n t cnt cnt 指数，不满足 c i t a t i o n s citations citations 的，故 r = m i d − 1 r = mid - 1 r=mid−1；
时间复杂度： O ( l o g 2 n ) O(log^2n) O(log2n)
C++代码：
class Solution {
public:int hIndex(vector<int>& citations) {int n = citations.size();int l = 0 , r = n;while(l < r){int mid = (l + r + 1) >> 1;auto it = lower_bound(citations.begin(),citations.end(),mid);int cnt = citations.end() - it;if(cnt >= mid) l = mid;else r = mid - 1;}return l;}
};