H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

https://leetcode.com/problems/h-index-ii/description/

Thoughts

h-index计算方法和paper的引用(数组元素值)和paper数目(数组长度)有关，我们自然可以往上面套。 我们可以先试几组数，[1, 2, 3, 4, 5]此时h-index为3，[1, 2, 4, 4, 5]此时h-index还是3. 从中我们可以看出两组都可以分成前后两部分，分界点都是第三个元素，前半部分皆满足数组长度-index （即达到该引用的paper数目）>元素值，因此可以构造二分法。

Code

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int start = 0, end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (n - mid > citations[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return n - start;
    }
}

Analysis

Errors:

1. return n - start. 不是start

一次二分法，时间复杂度O(lgn)