275. H-Index II

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

一刷
令len-h = left, 则N-left = h
用binary search在数组中寻找,nums[left]为小于h和大于h的交界。return len-left

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

二刷
思路和1刷相同

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

三刷
同上

public class Solution {
    public int hIndex(int[] citations) {
        int left = 0, len = citations.length, right = len-1, mid;
        while(left<=right){
            mid = left + (right-left)/2;
            if(citations[mid] >=(len-mid)) right = mid-1;
            else if(citations[mid] <(len-mid)) left = mid+1;
        }
        return len - left;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容