题解 | 寻找第K大

class Solution {
  public:
    int partition(vector<int>& a, int left, int right) {
        int pivot = a[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && a[j] <= pivot) j--;  
                a[i] = a[j]; 
            while (i < j && a[i] >= pivot) i++;
                a[j] = a[i];  
        }
        a[i] = pivot;
        return i;
    }

    int findKth(vector<int>& a, int n, int K) {
        int left = 0, right = n - 1;
        while (left <= right) {
            int pos = partition(a, left, right);
            int len_left = pos - left + 1;
            if (len_left == K) {
                return a[pos];
            } else if (len_left > K) {
                right = pos - 1;
            } else {
                K -= len_left;
                left = pos + 1;
            }
        }
        return -1;
    }
};

len_left计算左侧部分的元素个数（包括基准值）
情况1：找到目标
如果左侧长度正好等于K，说明基准值就是第K大的元素
直接返回 a[pos]

情况2：目标在左侧
如果左侧长度大于K，说明第K大的元素在左侧部分
缩小搜索范围到左侧：right = pos - 1

情况3：目标在右侧
如果左侧长度小于K，说明第K大的元素在右侧部分
调整K值：K -= len_left（因为我们已经找到了前len_left个最大的元素）
缩小搜索范围到右侧：left = pos + 1