题解 | #寻找第K大#

class Solution {
public:
  // 注意快速排序是要升序还是降序
  // 降序的话，i，j重合时的下标若为 k - 1，即为第k大的数字
  // 升序的话，i，j重合时的下标是第 i + 1 小的数字
    int quick_sort(vector<int>& vec, int begin, int end, int k){
        int tmp = vec[begin];	// 选择基准数，这里选的是下标为begin的数字（vec中第一个元素）
        int i = begin, j = end;
        while(i != j){	// i，j不相等时进入循环
            while(vec[j] <= tmp && j > i) --j;	// j从右往左找比基准数大的数字
            while(vec[i] >= tmp && j > i) ++i;	// i从左往右找比基准数小的数字
            if(j > i){	// 如果 j > i，则一直进行交换，直到i，j重合，此时i左边都是比基准数大的数
                int t = vec[i];
                vec[i] = vec[j];
                vec[j] = t;
            }
        }
	  // 此时i，j重合处的元素比基准数大，交换基准数与此元素
        vec[begin] = vec[i];
        vec[i] = tmp;
	  // 如果i是第k大的数，直接返回
        if(i == k - 1) return vec[i];
	  // 如果i比 k - 1大，说明第k大的数在i的左边，只需要递归i左边的数列
        if(i > k - 1) return quick_sort(vec, begin, i - 1, k);
	  // 如果i比 k - 1小，说明第k大的数在i的右边，只需要递归i右边的数列
        if(i < k - 1) return quick_sort(vec, i + 1, end, k);
	  // 最后的 return -1；是为了保证函数结构的准确性，实际不会运行这一句
        return -1;
    }
    int findKth(vector<int> a, int n, int K) {
        return quick_sort(a, 0, n - 1, K);
    }
};