一、知识点

数组 快排

二、解题思路

利用快排思想，第k小数前面都比它小，后面都比它大。

根据pos和k的相对位置，每次只继续处理一边的顺序。

时间复杂度O(n)，空间复杂度O(1)。

三、C++解法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int findKthSmallest(vector<int>& weights, int k) {
        int len = weights.size();
        int ret = quickSort(weights, 0, len - 1, k -1);
        return ret;
    }

    int quickSort(vector<int>& weights, int left, int right, int k) {
        int pos = findPos(weights, left, right);
        if (pos == k) {
            return weights[pos];
        } else if (pos < k) {
            return quickSort(weights, pos + 1, right, k);
        } else {
            return quickSort(weights, left, pos - 1, k);
        }
    }

    int findPos(vector<int>& weights, int left, int right) {
        int first = weights[left];
        while (left < right) {
            while (left < right && weights[right] >= first) {
                right --;
            }
            swap(weights[left], weights[right]);
            while (left < right && weights[left] <= first) {
                left ++;
            }
            swap(weights[left], weights[right]);
        }
        return left;
    }
};