一、题目

二、思路

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

三、题解

• 方法1

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;}
}

• 方法2

class Solution {public int hIndex(int[] citations) {int n = citations.length;int l = 1, r = n;// h 指数的取值受到论文篇数与论文引用次数的影响，显然通过论文篇数更好确定 h 指数的取值// 即 h 的取值范围：[0, n]// l 左边一定是符合条件的，r 右边一定是不符合条件的// 要找的是符合条件的最大值，那么返回 l - 1，也就是退出 while 循环时的 rwhile (l <= r) {int mid = l + (r -l)/2;if (citations[n - mid] >= mid) {// 说明第 n - mid, n - 2, n-1(最后一篇)一共mid篇的引用次数都是 >= mid的，说明 mid 取得值较小l = mid + 1;// 往右扩充 l 缩小查找范围} else {r = mid - 1;}}return r;}
}