【二分查找】力扣 275. H 指数 II

一、题目

二、思路

• h 指数是高引用引用次数，而 citations 数组中存储的就是不同论文被引用的次数，并且是按照升序排列的。也就是说 h 指数将整个 citations 数组分成了两部分，左半部分是不够引用 h 次 的论文，右半部分论文的引用次数都是大于等于 h 的。
• 因此，可以采用二分查找的思路来进行求解 h 指数。
• 需要注意的是：有时论文的引用次数并不一定是 citations 数组中的数值。
  • 例如：citations = [0, 1, 2, 4, 5, 6]，其 h 指数是 3。

三、题解

class Solution {public int hIndex(int[] citations) {int n = citations.length;int left = 0, right = n - 1;int ans = Math.min(1, citations[0]);// citations[0] 是引用次数最少的论文while (left <= right) {int mid = left + (right - left)/2;// n - mid 代表右半部分的数组，为符合条件的论文数量// 比较 符合条件的论文数量 和 citations[mid]// h 指数（ans）更新为二者中较小的if (n - mid > citations[mid]) {ans = Math.max(ans, citations[mid]);left = mid + 1;} else if (n - mid < citations[mid]) {ans = Math.max(ans, n - mid);right = mid - 1;} else {ans = citations[mid];break;}}return ans;}
}