My O(n) solution based on binary search


  • 0
    M
    public class Solution {
        
        private int[] testIndex(int val, int[] citations) {
            int[] res = new int[2];
            for(int i : citations) {
                if(i == val) res[1]++;
                if(i > val) {
                    res[0]++;
                    res[1]++;
                }
            }
            return res;
        }
        
        public int hIndex(int[] citations) {
            int lo = 0, hi = Integer.MAX_VALUE, max = 0;
            
            while(lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int[] range = testIndex(mid, citations);
                if(range[0] <= mid && mid <= range[1]) {
                    max = mid;
                    lo = mid+1;
                }else if(mid < range[0]) {
                    lo = mid+1;
                }else{
                    hi = mid - 1;
                }
            }
            
            return max;
        }
    }
    

    I am just performing a inary search for the vaue of h. It is aprox O(30 n) ~ O(n)


Log in to reply
 

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