Java solution using MaxHeap 7ms O(n)


  • 0
    Y
    	public int findKthLargest(int[] nums, int k) { // TC = O(n) + O (k* log n) = O(n)
    
    		buildMaxheap(nums); // TC = O(n)
    		int ret = 0;
    		for (int i = 0; i < k; i++) { // TC = O (k* log n)
    			ret = extractMax(nums, nums.length - i);
    		}
    		return ret;
    	}
    
    	void buildMaxheap(int[] nums) { // TC = O(n)
    		for (int i = nums.length / 2; i >= 0; i--)
    			heapify(nums, i, nums.length);
    	}
    
    	void heapify(int[] nums, int i, int length) {
    
    		int left = 2 * i + 1;
    		int right = 2 * i + 2;
    
    		int largestIndex;
    		if (left < length && nums[left] > nums[i])
    			largestIndex = left;
    		else
    			largestIndex = i;
    
    		if (right < length && nums[right] > nums[largestIndex])
    			largestIndex = right;
    
    		if (largestIndex != i) {
    			// swap
    			int temp = nums[largestIndex];
    			nums[largestIndex] = nums[i];
    			nums[i] = temp;
    
    			heapify(nums, largestIndex, length);
    		}
    
    	}
    
    	int extractMax(int[] nums, int length) { // TC = O(log n)
    		int max = nums[0];
    		// swap nums[0] and nums[length-i]
    		int temp = nums[0];
    		nums[0] = nums[length - 1];
    		nums[length - 1] = temp;
    
    		heapify(nums, 0, length - 1);
    		return max;
    
    	}
    

Log in to reply
 

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