寻找第K大

  • 快排变体
  • 第K大: pivot == K-1
    class Solution {
public:
  int findKth(vector<int> a, int n, int K) {
      if (K <= 0 || K > n) return -1;
      int l = 0, r = a.size() - 1;
      while (true) {
          int pivot = partition(a, l , r);
          if (pivot == K - 1) break;
          if (pivot < K - 1) l = pivot + 1;
          else r = pivot - 1;
      }
      return a[K-1];
  }
  int partition(vector<int> &nums, int l, int r) {
      int pivot = l;
      while (l != r) {
          while (l < r && nums[r] < nums[pivot]) r--;
          while (l < r && nums[l] >= nums[pivot]) l++;
          if (l < r) swap(nums[r], nums[l]);
      }
      swap(nums[l], nums[pivot]);
      return l;
  }
};