题解 | 寻找第K大

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    int partition(vector<int>& a, int start, int end) {
        int pivot = a[start];
        // cout << "pivot = " << pivot << endl;
        int i = start, j = end;

        while (i < j) {
            while(i < j && a[j] <= pivot) {
                --j;
            }
            if (i < j) {
                a[i] = a[j];
                ++i;
            }
            while(i < j && a[i] >= pivot) {
                ++i;
            }
            if (i < j) {
                a[j] = a[i];
                --j;
            }
        }
        a[i] = pivot;
        return i;
    }
    int findKth(vector<int>& a, int n, int K) {
        // write code here
        int l = 0, r = n-1;
        
        int pos = partition(a, l, r);
        // for (auto num : a) {
        //     cout << num << " ";
        // }
        // cout << endl;

        cout << pos << endl;
        while((pos+1) != K) {
            if ((pos+1) < K) {
                l = pos+1;
                pos = partition(a, l, r);
            }
            else {
                r = pos-1;
                pos = partition(a, l, r);
            }
        }

        // for (auto num : a) {
        //     cout << num << " ";
        // }
        // cout << endl;

        // cout << "pos = " << pos << endl;

        return a[pos];
    }
};

基于快排的划分函数，可以得到当前划分操作中枢轴元素所在位置：

1. 若该位置 == K，则找到第K大元素的位置
2. 若该位置 > K，则到当前划分位置的左边继续寻找
3. 若该位置 < K，则到当前划分位置的右边继续寻找

Day3