Leetcode 题目解析之 H-Index II

原创

ruochen

发布于 2022-01-10 20:19:53

1.3K0

发布于 2022-01-10 20:19:53

文章被收录于专栏：若尘的技术专栏若尘的技术专栏

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.

二分查找

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

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

algorithm