Leetcode 题目解析之 H-Index II

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

Hint:

• Expected runtime complexity is in O(log n) and the input is sorted.

二分查找

代码语言：txt复制

    public int hIndex(int[] citations) {
        int n = citations.length;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low   (high - low) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                low = mid   1;
            } else {
                high = mid - 1;
            }
        }
        return n - low;
    }

algorithm input runtime

0 人点赞