题目链接

AcWing 786.第k个数

引用

星丶空大佬的题解，很不错的思路，奇怪的思路+1 并没有
写一个和yxc大佬不同但差不多思想的方法，代码更简单

题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。

样例

输入格式

第一行包含两个整数 n 和 k。

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

输出格式

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

数据范围

1≤n≤1000001≤n≤100000,
1≤k≤n1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

算法

(快速选择) O(n)O(n)

从快排的性质可以知道，每次划分区间的时候j左边的数都是小于等于x的，右边的都是大于等于x的。所以如果左区间的长度大于等于k，那么第k个数必定在左区间，所以我们只需递归左区间，反过来，如果k大于左区间长度，那么第k个数在右区间，那么相对于右区间，第k个数在右区间中变为第（k - 左区间的长度）个数，然后递归右区间即可。

时间复杂度 O(n)O(n)

emmm，问就是不知道怎么算的，不过肯定比 O(nlogn)O(nlogn) 小，等我看了y总的时空复杂度分析再来补吧，哈哈哈

C++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n , k;
int a[N];

int quick_sort(int q[] , int l , int r , int k)
{
    if(l >= r) return q[l];
    
    int i = l - 1 , j = r + 1 , x = q[l + r >> 1];
    while(i < j)
    {
        do ++ i; while(q[i] < x);
        do -- j; while(q[j] > x);
        if(i < j) swap(q[i] , q[j]);
    }
    
    int len = j - l + 1;
    if(len >= k) return quick_sort(q , l , j , k);
    else return quick_sort(q , j + 1 , r , k - len);
}

int main()
{
    
    scanf("%d%d" , &n , &k);
    
    for(int i = 0; i < n; ++ i) scanf("%d" , &a[i]);
    
    int res = quick_sort(a , 0 , n - 1 , k);
    
    printf("%d" , res);
    
    return 0;
}