题目描述（中等难度）

275. H-Index II - 图1

求 H-Index，和 上一道题 一样，只不过这道题给定的数组是有序的，详细的可以先做一下上一题。

解法一

先看一下之前的其中一个的做法。

img

我们从 0 开始遍历，依次判断点是否在直线下方，如果出现了点在直线上方（包括在直线上），那么当前点的垂线与直线交点的纵坐标就是 H-Index 了。

点的垂线与直线交点的纵坐标的求法是 n - i，n 是数组长度，i 是数组下标。

代码如下。

  1. public int hIndex(int[] citations) {
  2.     Arrays.sort(citations);
  3.     int n = citations.length;
  4.     for (int i = 0; i < n; i++) {
  5.         // 点在直线上方
  6.         if (citations[i] >= n - i) {
  7.             return n - i;
  8.         }
  9.     }
  10.     return 0;
  11. }

说白了，我们是要寻找第一个在直线上方（包括在直线上）的点，给定数组是有序的，所以我们可以用二分查找。

  1. public int hIndex(int[] citations) {
  2.     int n = citations.length;
  3.     int low = 0;
  4.     int high = n - 1;
  5.     while (low <= high) {
  6.         int mid = (low + high) >>> 1;
  7.         //在直线上方
  8.         if (citations[mid] >= n - mid) {
  9.             if (mid == 0) {
  10.                 return n;
  11.             }
  12.             //前一个点是否在直线下方
  13.             int before = mid - 1;
  14.             if (citations[before] < n - before) {
  15.                 return n - mid;
  16.             }
  18.             high = mid - 1;
  19.         } else {
  20.             low = mid + 1;
  21.         }
  22.     }
  23.     return 0;
  24. }

总

主要就是二分查找的应用了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情