题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

输入样例

5 3
2 4 1 5 3

输出样例

3

算法1

快速选择算法

快排的每一趟，数轴的左边都会是 <= x 的， 右边都是 >= x 的。
左边元素的个数是 s1 = j - l + 1, 如果k <= s1 的话，那么下次递归的区间就是左边，否则右边。
直到 l == r 时返回q[l]。

时间复杂度

O(n)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int n, k;
int q[N];

int quick_sort(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 s1 = j - l + 1;
    if(k <= s1) quick_sort(l, j, k);
    else quick_sort(j + 1, r, k- s1);
}

int main(){
    cin >> n >> k;

    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    cout << quick_sort(0, n - 1, k) << endl;

    return 0;
}

算法2

参考

一个和yxc大佬不同但差不多思想的方法，代码更简单