题解 | #第k轻的牛牛#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是如何在一个数组中找到第 k 小的元素。

题目解答方法的文字分析

题目要求我们设计一个时间复杂度为 O(n) 的算法，找出数组中第 k 小的元素。我们可以使用快速选择算法来实现这一目标。

快速选择算法的思路类似于快速排序，但我们只关心一侧的子数组，以便减少问题规模。

具体步骤如下：

1. 随机选择一个元素作为基准元素（pivot）。
2. 将数组划分为小于等于基准元素和大于基准元素两部分。
3. 如果基准元素的下标等于 k - 1，表示找到了第 k 小的元素，直接返回基准元素。
4. 如果基准元素的下标大于 k - 1，说明第 k 小的元素在基准元素的左侧，继续在左侧子数组中寻找。
5. 如果基准元素的下标小于 k - 1，说明第 k 小的元素在基准元素的右侧，继续在右侧子数组中寻找。

本题解析所用的编程语言 (C++)

本题解析所用的编程语言是 C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int findKthSmallest(vector<int>& weights, int k) {
        // 调用快速选择算法，寻找第 k 小的元素
        return quickSelect(weights, 0, weights.size() - 1, k - 1);
    }

private:
    int quickSelect(vector<int>& arr, int left, int right, int k) {
        // 使用快速选择算法在数组 arr 中寻找第 k 位置的元素
        int pivotIndex = partition(arr, left, right);

        if (pivotIndex == k) {
            return arr[pivotIndex]; // 基准元素正好是第 k 小的元素
        } else if (pivotIndex < k) {
            // 基准元素在第 k 位置的右侧，继续在右侧子数组中寻找
            return quickSelect(arr, pivotIndex + 1, right, k);
        } else {
            // 基准元素在第 k 位置的左侧，继续在左侧子数组中寻找
            return quickSelect(arr, left, pivotIndex - 1, k);
        }
    }

    int partition(vector<int>& arr, int left, int right) {
        // 使用快速排序的分区方法，划分数组并返回基准元素的位置
        int pivot = arr[right]; // 选择最右侧的元素作为基准元素
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }

        swap(arr[i + 1], arr[right]); // 将基准元素放到正确的位置
        return i + 1;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！