The 2 ending point choice analysis !


  • 0

    By analyzing the condition

       citations[i] >= len-i  then return (len-i)
    

    So, WE want to find the biggest (len-i)

    when i=-1 we can never satisfy citations[i] >= len+1

    when i=len we can satisfy citations[len] >= 0

    So we choose the field like this

        (-1, len]  
    

    Here is the code:

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int len=citations.size();
            if(len==0)  return 0;
            return binarySearch(citations);
        }
        
        int binarySearch(vector<int>& v){
            int len=v.size();
            int start=-1, end=len;
            int mid=0;
            while(end-start>1){
                mid=(start+end)/2;
                if(v[mid]>=len-mid)  end=mid;
                else start=mid;
            }
            return len-end;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.