215. Kth Largest Element in an Array -M !!!

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.

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到中间的操作。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // half of the quick sort
        int n = nums.size();
        if(k == 1){
            auto max_iter = max_element(nums.begin(), nums.end());// get max
            return *max_iter;
        }
        int mid = (nums.front() + nums.back()) / 2;// first get mid of first and last
        vector<int> bigger, smaller;
        int midCount = 0;
        for(const auto & val : nums){
            if( val > mid){
                bigger.push_back(val);// move to new and pop it out
            }else if(val == mid){
                midCount++;
            }else{
                smaller.push_back(val);
            }
        }
        if(bigger.size()>=k){
            return findKthLargest(bigger, k);
        }else if(bigger.size() + midCount >= k){
            return mid;
        }else{
            return findKthLargest(smaller, k- bigger.size() - midCount);
        }
    }
};

这个题目，自己第一次做的时候， 没有做把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];
    }
};