Leetcode.215 c++归并排序，看这一个题就够了！

[215. 数组中的第K个最大元素]

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
利用归并排序的思想：例如输入[1,2,7,5,8,9]：

图示

具体代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        change_list(nums,0,nums.size()-1);
        return nums[k-1];
    }
private:
    void change_list(vector<int>& nums,int l,int r){
        if(l==r) return;
        int m = (l+r)/2;
        change_list(nums,l,m);
        change_list(nums,m+1,r);
        int lr=l,rr=m+1;
        vector<int> tmp;
        while(lr<=m && rr<=r){
            if(nums[lr]>=nums[rr]){
                tmp.push_back(nums[lr]);
                lr++;
            }
            else{
                tmp.push_back(nums[rr]);
                rr++;
            }
        }
        while(lr<=m){
                tmp.push_back(nums[lr]);
                lr++;
        }

        while(rr<=r){
                tmp.push_back(nums[rr]);
                rr++;
        }
        for(int i=l;i<=r;i++) nums[i]=tmp[i-l];
        return;
    }
};