acwing786. 第k个数

题目

题解

我们知道，快速排序每次可以确定一个基准的位置，例如当前基准为第五个数，那么可以将比这个数小的前四个数都放在前面，比这个数大的都放在后面，比如
a[5]=[3,2,4,1,5]要寻找第2大的数：
首先假如以a[2]=4作为基准，那么就变成a[2,1,3,4,5]
此时a[2]是第4大的数，要找第二大的话，就需要到4这个数前面的前面去找

即：
if(j-l+1>=k)return quick_sort(l,j,k);//要找的第k个数比基准值小，就去前半部分寻找
else return quick_sort(j+1,r,k-(j-l+1));////要找的第k个数比基准值大，就去后半部分寻找

#include<iostream>
using namespace std;
const int N = 100010;
int n,k,a[N];
int quick_sort(int l,int r,int k){
    if(l>=r)return a[l];
    int i=l-1,j=r+1;
    int x=a[(l+r)>>1];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    if(j-l+1>=k)return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k-(j-l+1));
}

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