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)來維護(hù)當(dāng)前前k個(gè)大的元素淑际，輸出第k個(gè)
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個(gè)大的元素担败，輸出第k個(gè)
思路：
Time Complexity: O(N + k * logN) Space Complexity: O(N)
Solution4：類似快排的Partition
思路：因?yàn)槭且业降趉個(gè)大的元素掩缓，所以每次以一個(gè)pivot來重排數(shù)組料仗，使得大于pivot的元素在pivot的左邊，小于pivot的元素在pivot的右邊意敛，
實(shí)現(xiàn)過程類似快速排序(前后雙指針馅巷，比較，交換)草姻，
比如原數(shù)組為nums = [*3, 1, 2, 4, 5]钓猬，如選中3作為pivot(選pivot的過程有隨機(jī)成分，這也是有可能出現(xiàn)worse case的原因)撩独，一次重排后數(shù)組變?yōu)椋?br>
nums = [5, 4, 3, 2, 1]敞曹，將pivot=3的位置記為pos，若此時(shí)k - 1 < pos综膀，說明第k個(gè)大的元素肯定在左邊部分澳迫，
所以后續(xù)只需要在左邊部分[5,4]重復(fù)選擇pivot重排的過程；相反同理僧须，若k - 1 > pos纲刀，則在右邊部分重排..；若k == pos直接返回担平。
這樣一來示绊，如果pivot選的數(shù)(隨機(jī)成分)接近median，相當(dāng)于每次二分暂论，則：T(n) = T(n/2) + O(n)面褐，O(n)是重排的過程，可解得T(n) = O(n)取胎。
實(shí)現(xiàn)上：可剛開始在輸入上shuffle一下展哭，保證"更加無序"
所以Average是近似二分湃窍，時(shí)間復(fù)雜度 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);
}
}
}
