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.
You may assume k is always valid, 1 ≤ k ≤ array's length.
A:
--------用maxHeap ---------O(n+k*log(k))-----------------class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); // need a min heap, thus the top() is the minimum to remove priority_queue<int, vector<int>, greater<int> > q; // default is less, which result into max queue for(auto v : nums) { q.push(v); if(q.size()>k) q.pop(); } return q.top(); } };
QuickSelect
(这道题的关键点在于 当值全部大于（或小于）pivot点的时候的处理方式。--》 因此要把pivot点swap到中间的操作。
public class Solution {
public int findKthLargest(int[] nums, int k) {
return helper(nums,k ,0,nums.length -1);
}
private int helper(int[] A, int k, int start, int end){
if(start == end )
return A[start];
int mid = end ; // mid is the first index that A[mid] >= pivot
for(int i =start; i< mid;i++){
if(A[i]>=A[end]){
mid--;
swap2(A,i,mid);
i--;
}
}
swap2(A,mid,end);
int nRight = end - mid+1; // number of Elements that are > pivot
if( k == nRight ) // start and end are both smallest
return A[mid];
// if(mid == end) // this can never happen
else if( k < nRight )
return helper(A,k,mid+1,end);
else
return helper(A, k-nRight, start, mid-1);
}
private void swap2(int[] A, int i ,int j){
int tmp = A[i]; // switch
A[i] = A[j];
A[j] = tmp;
}
}
这个题目，自己第一次做的时候， 没有做把end的值swap到mid位置的操作，因此会出现死循环。
Mistakes:
1: 当k ==1的时候，还是要继续分下去。 而基础条件应该是 start == end
2:
double pivot = (A[start] + A[end])/2;这里，当A[start] == 1, A[end]==2的 时候，pivot 的结果是1. ！！！！！
因此要除以 2.0
------------------------排序------- 但是对于太大的数组，不适合--------------------
class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size()-k]; } };
