acwing算法基础之基础算法--快速选择算法

1 知识点

快速选择算法基于快速排序算法，用于求解第k小的数，它的时间复杂度为O(n)。
算法步骤如下：

1. 选取分界点x，设置为nums[(l+r)/2]。
2. 重排数组，使得左边部分的都小于等于x，右边部分的都大于等于x。
3. 如果k小于等于左边部分长度$s_l$，则递归左边部分；否则递归右边部分，求第$k-s_l$小的数。

2 模板

//nums为原数组
//返回第k小的数，k从1开始
int quick_select(vector<int> &nums, int l, int r, int k) {
    if (l == r) {
        return nums[l];
    }
    
    int x = nums[(l+r)/2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j) {
            swap(nums[i], nums[j]);
        }
    }
    int sl = j - l + 1;
    if (sl >= k) {
        return quick_select(nums, l, j, k);
    } else {
        return quick_select(nums, j+1, r, k-sl);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23