Share my sulution with heap sort idea


  • 0
    C
    public int findKthLargest(int[] nums, int k) {
        // build max heap
        for(int i = nums.length / 2; i >= 0; i--)
        	percDown(nums, i, nums.length);
        // do k - 1  op of deleteMax()
        for(int i = 1; i < k; i++){
            // put the max element into the last valid heap position
        	int temp = nums[nums.length - i];
        	nums[nums.length - i] = nums[0];
        	nums[0] = temp;
            // adjust heap
        	percDown(nums, 0, nums.length - i);
        }
        return nums[0];
    }
    private int leftChild(int i){
    	return 2 * i + 1;
    }
    private void percDown(int[] nums, int i, int length){
    	int child;
    	int temp;
    	for (temp = nums[i]; leftChild(i) < length; i = child) {
    		child = leftChild(i);
    		if(child != length - 1 && nums[child] < nums[child + 1])
    			child++;
    		if(nums[child] > temp)
    			nums[i] = nums[child];
    		else
    			break;
    	}
    	nums[i] = temp;
    }

Log in to reply
 

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