题解 | #第k轻的牛牛#

考察知识点：快速选择

题目分析：

题目要求在O(n)的时间复杂度下找到第k轻的牛牛，很明显应使用快速选择算法。

快速选择算法基于快速排序的思想。首先选取一个基准值，将数组中小于基准值的数放到左边，大于基准值的数放到右边。

为了不产生死循环，我们每次首先让i和j移动一位，然后再判断条件是否满足，是否可以继续移动。

最终当 i >= j 时停止，此时判断 j 和 k 的位置关系。

可以看到最终索引值比 j 小或等于 j 的数都是不大于基准值的。而范围 0 ~ i 中第i个数可能最终大于基准值。（依赖于快速选择算法的具体实现，其他实现方式可能会有所不同）。然后根据第k小的数是在范围 l ~ j 还是 j + 1 ~ r 进行递归查找。

时间复杂度：

平均情况下，每次分隔区间时，第一次遍历n个元素，第二次只需遍历n / 2个元素，第三次只需遍历n / 4个元素...那么时间复杂度是一个等比数列。设总共需要分隔x次：

而，故平均情况下时间复杂度近似为O(n)

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int quick_select(vector<int> &weights, int l, int r, int k) {
        if (l == r) return weights[l];
        int i = l - 1, j = r + 1, v = weights[l];
        while (i < j) {
            do i++; while (weights[i] < v);
            do j--; while (weights[j] > v);
            if (i < j) swap(weights[i], weights[j]);
        }
        if (k - 1 <= j) return quick_select(weights, l, j, k);
        else return quick_select(weights, j + 1, r, k);
    }
    int findKthSmallest(vector<int>& weights, int k) {
        // write code here
        int size = weights.size();
        int res = quick_select(weights, 0, size - 1, k);
        return res;
    }
};