知识点

快速选择

思路

要求时间复杂度为O(n)，我们可以使用快速选择算法解决。

快速选择算法是在快速排序算法的基础上，选择整个数组中第k小的数。

如果k \leq S_L 那么结果一定出现在左半边，只需要递归left一共SL个数字

如果 k \geq S_L 那么结果一定出现在右半边 ，只需要递归right一共k-SL个数

时间复杂度

n\;+\;n/2\;+\;n/4\;+\;...\;=\;O(n)

AC code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int findKthSmallest(vector<int>& weights, int k) {
        int n = weights.size();
        return quick_sort(weights, 0, n - 1, k);
    }
    // 快速选择算法
    int quick_sort(vector<int> q, int l, int r, int k) {
        if (l >= r) return q[l];
        int x = q[l], i = l - 1, j = r + 1;
        while(i < j) {
            while (q[++i] < x);
            while (q[--j] > x);
            if (i < j) swap(q[i], q[j]);
        }
        int sl = j - l + 1;
        if (k <= sl) return quick_sort(q, l, j, k);
        return quick_sort(q, j + 1, r, k-sl);
    }
};