题解 | #寻找第K大#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型vector
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    int findKth(vector<int>& a, int n, int K) {
        //快速排序每一趟确定一位元素的最终位置，
        //如果a[i]=x，则说明，第i+1大的数是x,第K大的数，位置就在K-1
        //同理我们根据此原理（降序）二分数组为Sa、Sb，假设本趟确定的位置是y(y>k-1)
        //则说明我们要找的数在数组Sa之中
        //由此循环反复，直到确定a[K-1] = z ，z即为所求
        int low = 0, high = n - 1;
        int low_ = low, high_ = high;

        while (low < high) {
            int mid_val = a[low];

            //一趟
            while (low < high) {
                //比枢纽元素大的，放到左边
                while (low < high && a[high] <= mid_val) high--;
                a[low] = a[high];
                while (low < high && a[low] >= mid_val) low++;
                a[high] = a[low];
            }

            a[low] = mid_val;

            // cout << low << " " << a[low] << endl;
            //找到了
            if (low == K - 1) {
                break;
            } else if ( low > K - 1) {
                //保留SA
                low = low_;
                high_ = --high;
            } else if (low < K - 1) {
                //保留SB
                high = high_;
                low_ = ++low;
            }
        }

        return a[K - 1];
    }
};