acwing-第k个数

第k个数

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

输入格式

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

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

输出格式

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

---

最暴力的做法是把数组全部排序然后输出。

但其实可以不用全部排序，只排列一部分就能得到答案。

每趟排序后pivot左边的数全部小于等于pivot，右边的数全部大于等于pivot。所以每趟排序后判断j 和k的关系，决定排序哪一边。

#include<iostream>
#define N 100000
using namespace std;
int a[N];

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

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int a=quick_select(0,n-1,k);
    cout<<a<<" ";
    return 0;
}