Java solution -- heap sort


  • 0
    P
    public int findKthLargest(int[] nums, int k) {
        for(int i=nums.length/2; i>0; i--) 
            maxHeapify(nums, i, nums.length);
        
        for(int i=1; i<k; i++) {
            int tmp = nums[nums.length-i];
            nums[nums.length-i] = nums[0];
            nums[0] = tmp;
            
            maxHeapify(nums, 1, nums.length-i);
        }
        return nums[0];
    }
    
    void maxHeapify(int[] nums, int index, int size) {
        int left = index<<1, right = (index<<1)+1;
        int max = index;
        
        if(left<=size && nums[left-1]>nums[max-1]) max = left;
        if(right<=size && nums[right-1]>nums[max-1]) max = right;
        if(max!= index) {
            int tmp = nums[max-1];
            nums[max-1] = nums[index-1];
            nums[index-1] = tmp;
            
            maxHeapify(nums, max, size);
        }
    }

Log in to reply
 

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