[LeetCode] 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 <= k <= array's length.

Thought process:

Divide and conquer. Quick select. Use the partition algorithm from quick sort to sort the array in descending order. After partitioning, there are three cases for the pivot:

1. Pivot == k: found the kth largest element.
2. Pivot < k: keep searching on the right side.
3. Pivot > k: keep searching on the left side.

Solution 1 (quick select):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { private Random random = new Random(); public int findKthLargest(int[] nums, int k) { return partition(nums, k, 0, nums.length - 1); } private int partition(int[] nums, int k, int left, int right) { int pivot = left + random.nextInt(right - left + 1); swap(nums, pivot, right); int i = left; for (int j = left; j < right; j++) { if (nums[j] > nums[right]) { swap(nums, i, j); i++; } } swap(nums, i, right); if (i < k - 1) { return partition(nums, k, i + 1, right); } else if (i == k - 1) { return nums[i]; } else { return partition(nums, k, left, i - 1); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

Time complexity: O(n) with random pivot.

I could also use a heap. Use a min heap of size k to store k largest numbers so far.

Solution 2 (heap):

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int num : nums) { heap.offer(num); if (heap.size() > k) { heap.poll(); } } return heap.poll(); } }

Time complexity: O(nlogn).