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

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

 

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

 

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

A:

--------用minHeap  ---------O(n+k*log(k))-----------------

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // Internally, priority_queue uses a max-heap with operator<, so:
    // If a < b, then b has higher priority
        priority_queue<int, vector<int>, greater<int>> queue;
        for(auto v : nums){
            queue.push(v);
            if(queue.size() > k){
                queue.pop();
            }
        }
        return queue.top();
    }
};

QuickSelect
(这道题的关键点在于 当值全部大于（或小于）pivot点的时候的处理方式。--》 因此要把pivot点swap到中间的操作。

核心是要数 midVal的个数。 这样方便砍掉

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位置的操作，因此会出现死循环。

——————————第三遍————————————
quick sort 思路。 

就是本地数组操作，避免了copy 一个新的数组

class Solution {

public:

int findKthLargest(vector<int>& nums, int k) {

// since more familiar with count from small to large

return helper(nums, 0, nums.size(), nums.size() + 1 - k);

}

private:

int helper(vector<int>& nums, int start, int end, int k) {

int pivot = nums[start], cPivot = 0;

int latestSmall = start - 1, latestBigger = end;

for (int i = start; i < latestBigger; i++) {

if (nums[i] > pivot) {

--latestBigger;

if (i != latestBigger) {

swap(nums[latestBigger], nums[i]);

i--;

}

} else if (nums[i] == pivot) {

cPivot++;

} else {

swap(nums[++latestSmall], nums[i]); // no need to i--

}

}

int l = latestSmall - start + 1;

int r = end - latestBigger;

if (k <= l) { // use left part

return helper(nums, start, latestSmall + 1, k);

} else if (k > l + cPivot) {

return helper(nums, latestBigger, end, k - l - cPivot);

} else {

return pivot;

}

}

};

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];
    }
};