题解 | #寻找第K大#

有用例不通过，快排退化的时候不通过！ 这里用一点小技巧防止快排退化。

class Solution {
  public:
    int findKth(vector<int> a, int n, int K) {
      return quick_sort(a, 0, a.size() - 1, K);
    }
  private:
    int quick_sort(std::vector<int> &res, int low, int high, int k) {
      int i = low, j = high, target = (low + high) >> 1;
        //  防止快排退化
      std::swap(res[low], res[target]);
      
      while (i < j) {
        while (i < j && res[i] >= res[low]) {
          ++i;
        }
        while (i < j && res[j] <= res[low]) {
          --j;
        }
        
        if (i < j) {
          std::swap(res[i++], res[j--]);
        }
      }
      
      if (res[i] < res[low]) {
        --i;
      }
      
      std::swap(res[i], res[low]);
      
      if (i - low + 1 == k) {
        return res[i];
      }
      
      if (i - low + 1 > k) {
        return quick_sort(res, low, i - 1, k);
      } else {
        return quick_sort(res, i + 1, high, k - (i - low + 1));
      }
    }
};