题解 | #寻找第K大#

使用归并排序来解决问题：先将前半个数组排序，后将后半个数组排序

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        mearge(a, 0, n - 1);
        return a[K-1];
    }
    void mearge(vector<int>& a, int l, int r) {
        vector<int> res; // 创建一个数组来存储将两个归并数组重新排列后的结果
        if(l >= r) return ;
        int mid = (l + r) / 2;
        mearge(a, l, mid);
        mearge(a, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r) {
            if(a[i] > a[j])    res.push_back(a[i++]);
            else    res.push_back(a[j++]);
        }
        while(i <= mid) res.push_back(a[i++]);
        while(j <= r) res.push_back(a[j++]);

        for(int i = l, j = 0; i <= r; i++, j++) a[i] = res[j]; // 将归并排序后的结果更新到原数组中
    }
};