H-Index II

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

Analysis

• h index：有h篇文章citation 至少是h
• For example, citations = [0, 1, 3, 4, 5, 6], should return h-index = 4.
• 简单逻辑，从右边开始找，有1篇大于6，2篇大于5，3篇大于4，4篇大于3-->找到，return4
• 节省时间Use binary search: 每一次check $$citations[mid]$$和$$len-mid$$的关系。 len-mid代表有几篇paper的citiation大于等于citations[mid]
  • $$citations[mid]==len-mid$$:len-mid或者citations[mid]就是h-index的定义，返回
  • $$citations[mid] > len-mid$$:paper数量不够去左边找
  • $$citations[mid] <len-mid$$:paper数量太多去右边找

Code

public class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        int low = 0, high = len;

        while (low<high){
            int mid = low + (high-low)/2;
            if (citations[mid]==len-mid) {return citations[mid];}
            else if(citations[mid]>(len-mid)){high = mid;}
            else {low = mid+1;}
        }

        return len-high;

    }
}