题目描述(中等难度)

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

解法一

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

img

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

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

代码如下。

public int hIndex(int[] citations) {
    Arrays.sort(citations);
    int n = citations.length;
    for (int i = 0; i < n; i++) {
        // 点在直线上方
        if (citations[i] >= n - i) {
            return n - i;
        }
    }
    return 0;
}

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

public int hIndex(int[] citations) {
    int n = citations.length;
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        //在直线上方
        if (citations[mid] >= n - mid) {
            if (mid == 0) {
                return n;
            }
            //前一个点是否在直线下方
            int before = mid - 1;
            if (citations[before] < n - before) {
                return n - mid;
            }

            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}

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

results matching ""

    No results matching ""