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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
1. 在数组区间随机取`pivot index = left + random[right-left]`.
2. 根据pivot 做 partition，在数组区间，把小于pivot的数都移到pivot左边。
3. 得到pivot的位置 index，`compare(index, (n-k))`.
a. index == n-k -> 找到第`k`大元素，直接返回结果。
b. index < n-k -> 说明在`index`右边，继续找数组区间`[index+1, right]`
c. index > n-k -> 那么第`k`大数在`index`左边，继续查找数组区间`[left, index-1]`.
例子，【3,2,3,1,2,4,5,5,6]， k = 4
如下图：
class KthLargestElementSort {
public int findKthlargest2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
class KthLargestElementHeap {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.poll();
}
}
class KthLargestElementQuickSelect {
static Random random = new Random();
public int findKthLargest3(int[] nums, int k) {
int len = nums.length;
return select(nums, 0, len - 1, len - k);
}
private int select(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
// random select pivotIndex between left and right
int pivotIndex = left + random.nextInt(right - left);
// do partition, move smaller than pivot number into pivot left
int pos = partition(nums, left, right, pivotIndex);
if (pos == k) {
return nums[pos];
} else if (pos > k) {
return select(nums, left, pos - 1, k);
} else {
return select(nums, pos + 1, right, k);
}
}
private int partition(int[] nums, int left, int right, int pivotIndex) {
int pivot = nums[pivotIndex];
// move pivot to end
swap(nums, right, pivotIndex);
int pos = left;
// move smaller num to pivot left
for (int i = left; i <= right; i++) {
if (nums[i] < pivot) {
swap(nums, pos++, i);
}
}
// move pivot to original place
swap(nums, right, pos);
return pos;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
