【每日一题Day362】LC274H 指数 | 二分答案
H 指数【LC274】
给你一个整数数组
citations，其中citations[i]表示研究者的第i篇论文被引用的次数。计算并返回该研究者的h指数。根据维基百科上 h 指数的定义：
h代表“高引用次数” ，一名科研人员的h指数 是指他（她）至少发表了h篇论文，并且每篇论文 至少 被引用h次。如果h有多种可能的值，h指数 是其中最大的那个。
来晚了 奔波的一天
-
思路
- 二段性：存在最大值y使，少于等于y的数值一定满足条件；大于y的数值一定不满足条件
- 二分答案y
- 引用次数大于等于y的论文数目大于等于y，那么向右搜索获得更大的y
- 引用次数大于等于y的论文数目小于y，那么向左搜索获得更大的y
- check:排序后可以快速算出引用次数大于等于y的论文数目
-
实现
class Solution {public int hIndex(int[] citations) {int n = citations.length;Arrays.sort(citations);int l = 1, r = n;int res = 0;while (l <= r){int mid =(l + r) >> 1;if (check(citations, mid) >= mid){res = Math.max(res, mid);l = mid + 1; }else{r = mid - 1;}}return res;}public int check(int[] citations, int target){int n = citations.length;int l = 0, r = n - 1;while (l <= r){int mid = l + r >> 1;if (citations[mid] < target){l = mid + 1;}else{r = mid - 1;}}// l为第一个符合的下标return n - l;// 大于等于target的引用次数的数目} }- 复杂度
- 时间复杂度： O ( n l o g m ) O(nlogm) O(nlogm)， n n n是数组的长度，m是二分查找的上界。二分查找的时间复杂度是 O ( l o g m ) O(logm) O(logm)，每次判断需要的时间复杂度为 O ( n ) O(n) O(n)
- 空间复杂度： O ( log n ) O(\log n) O(logn)
- 复杂度