有序数组中的h引用 H-Index II

原创
2017/12/19 11:17
阅读数 31

问题:

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

解决:

① 给定的是有序数组,就不需要排序了。

class Solution {//139ms
    public int hIndex(int[] citations) {
        for (int i = 0;i < citations.length;i ++){
            if (citations.length - i <= citations[i]){
                return citations.length - i;
            }
        }
        return 0;
    }
}

② 二分搜索。

class Solution { //12ms
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        int len = citations.length;
        int left = 0;
        int right = len - 1;
        while (left <= right){
            int mid = (right - left) / 2 + left;
            int count = len - mid;
            if (citations[mid] == count){
                return count;
            }else if (citations[mid] > count){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return len - left;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部