Average time O(n), space O(1)


  • -3
    Z
    // actually is to find the frist element (in order) whose value larger than the rest of length
        public int hIndex(int[] c) {
            int size = c.length;
            int begin = 0;
            int end = size - 1;
            
            while (begin <= end)
            {
                int q = partition(c, begin, end);
                int len = size - q;
                
                if (c[q] >= len)
                    end = q - 1;
                else 
                    begin = q + 1;
            }
            
            return size - begin;
        }
        
        public int partition(int[] nums, int begin, int end)
        {
            int pivot = nums[begin];
            int small = begin;
            int large = end;
            
            while(small < large)
            {
                while(small < large && nums[large] >= pivot) large --;
                nums[small] = nums[large];
                while(small < large && nums[small] <= pivot) small ++;
                nums[large] = nums[small];
            }
            
            nums[large] = pivot;
            return large;
        }

Log in to reply
 

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