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
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.
You may assume k is always valid, 1 ≤ k ≤ array's length.
Solution: A naive way is to first sort the array in the decreasing (non-increasing) order, and then return the kth element. This takes O(n log n) time at best, where n = array's length.
Quickselect is a selection algorithm to efficiently find the kth largest/smallest element in an unsorted array. Below is an implementation of the quickselect algorithm, both recursive and iterative.
Further reading: Selection algorithm.
Complexity: O(n) on average, where n = array's length.
Code in Java:
Recursive version.
Quickselect is a selection algorithm to efficiently find the kth largest/smallest element in an unsorted array. Below is an implementation of the quickselect algorithm, both recursive and iterative.
Further reading: Selection algorithm.
Complexity: O(n) on average, where n = array's length.
Code in Java:
Recursive version.
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | public class Solution { private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; return; } private int partition( int[] nums, int low, int high, int pivotIdx ) { int pivotVal = nums[pivotIdx]; swap(nums, pivotIdx, high); int storeIdx = low; for (int i = low; i < high; i++) { if (nums[i] > pivotVal) { swap(nums, storeIdx, i); storeIdx++; } } swap(nums, storeIdx, high); return storeIdx; } private int findKthLargest( int[] nums, int low, int high, int k ) { if (low == high) { return nums[low]; } int offset = new java.util.Random().nextInt( high - low + 1 ); int pivotIdx = low + offset; pivotIdx = partition(nums, low, high, pivotIdx); if (pivotIdx == k) { return nums[k]; } if (pivotIdx > k) { return findKthLargest(nums, low, pivotIdx - 1, k); } else { return findKthLargest(nums, pivotIdx + 1, high, k); } } public int findKthLargest(int[] nums, int k) { return findKthLargest(nums, 0, nums.length - 1, k - 1); } } |
Iterative version.
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | public class Solution { private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; return; } private int partition( int[] nums, int low, int high, int pivotIdx ) { int pivotVal = nums[pivotIdx]; swap(nums, pivotIdx, high); int storeIdx = low; for (int i = low; i < high; i++) { if (nums[i] > pivotVal) { swap(nums, storeIdx, i); storeIdx++; } } swap(nums, storeIdx, high); return storeIdx; } private int findKthLargest( int[] nums, int low, int high, int k ) { if (low == high) { return nums[low]; } while (true) { int offset = new java.util.Random().nextInt( high - low + 1 ); int pivotIdx = low + offset; pivotIdx = partition(nums, low, high, pivotIdx); if (pivotIdx == k) { return nums[k]; } if (pivotIdx > k) { high = pivotIdx - 1; } else { low = pivotIdx + 1; } } } public int findKthLargest(int[] nums, int k) { return findKthLargest(nums, 0, nums.length - 1, k - 1); } } |
No comments:
Post a Comment