Java O(logN) solution using binary search


  • 0
    M

    Idea:
    Use binary search to find the first number that greater than its reversed index

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

Log in to reply
 

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