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.
Solution1：Sort后输出nums[k - 1]
思路：升序排序nums后，直接输出nums[k - 1]。
Time Complexity: O(NlogN) Space Complexity: O(1)
Solution2：最小堆过滤
思路：最小堆过滤，建立min_heap(size：k)来维护当前前k个大的元素，输出第k个
The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
poll() Retrieves and removes the head
C++: std::priority_queue default: max heap,
java/python: priorityqueue: min-heap
Time Complexity: O(k + Nlogk) , k: 建堆
Space Complexity: O(k) (Since可以直接在原序列上做：O(1))
Solution2.5：最小堆过滤 Round1
Time Complexity: O(k + Nlogk) , k: 建堆
Space Complexity: O(k) (Since可以直接在原序列上做：O(1))
Solution3：堆排序，建立max_heap(size：N)来排出k个大的元素，输出第k个
思路：
Time Complexity: O(N + k * logN) Space Complexity: O(N)
Solution4：类似快排的Partition
思路：因为是要找到第k个大的元素，所以每次以一个pivot来重排数组，使得大于pivot的元素在pivot的左边，小于pivot的元素在pivot的右边，
实现过程类似快速排序(前后双指针，比较，交换)，
比如原数组为nums = [*3, 1, 2, 4, 5]，如选中3作为pivot(选pivot的过程有随机成分，这也是有可能出现worse case的原因)，一次重排后数组变为：
nums = [5, 4, 3, 2, 1]，将pivot=3的位置记为pos，若此时k - 1 < pos，说明第k个大的元素肯定在左边部分，
所以后续只需要在左边部分[5,4]重复选择pivot重排的过程；相反同理，若k - 1 > pos，则在右边部分重排..；若k == pos直接返回。
这样一来，如果pivot选的数(随机成分)接近median，相当于每次二分，则：T(n) = T(n/2) + O(n)，O(n)是重排的过程，可解得T(n) = O(n)。
实现上：可刚开始在输入上shuffle一下，保证"更加无序"
所以Average是近似二分，时间复杂度 Average: O(N), Worst: O(NN)
Space Complexity: O(1)
Solution1 Code：
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
Solution2 Code：
class Solution {
public int findKthLargest(int[] nums, int k) {
final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.offer(val);
if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
}
Solution2.5 Code：
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums == null || nums.length < k) return -1;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < k; i++) {
pq.offer(nums[i]);
}
for(int i = k; i < nums.length; i++) {
if(nums[i] > pq.peek()) {
pq.poll();
pq.offer(nums[i]);
}
}
return pq.peek();
}
}
Solution3 Code：
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
// build max-heap
for(int val : nums) {
pq.offer(val);
}
// pop k times
int result = 0;
for (int i = 0; i < k; i++) {
result = pq.poll();
}
return result;
}
}
Solution4 Code：
class Solution {
public int findKthLargest(int[] nums, int k) {
// shuffle(nums);
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}
private int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && less(a[++i], a[lo]));
while(j > lo && less(a[lo], a[--j]));
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private boolean less(int v, int w) {
return v < w;
}
// Reservoir Sampling
private void shuffle(int a[]) {
final Random random = new Random();
for(int ind = 1; ind < a.length; ind++) {
final int r = random.nextInt(ind + 1);
exch(a, ind, r);
}
}
}
