谁来帮我看看是咋回事

P1923 【深基9.例4】求第 k 小的数

2115lhx @ 2022-09-14 16:17:19

#include<iostream>
using namespace std;
int m,n;
int a[5000002];
void sort(int l,int r) {
    if(l>=r)return ;
    int x=a[(l+r)/2],i=l-1,j=r+1;
    while(i<j) {
        do i++;
        while(x>a[i]);
        do j--;
        while(x<a[j]);
        if(i<j)swap(a[i],a[j]);
    }
    sort(l,j);
    sort(j+1,r);
}
int main() {
    cin>>m>>n;
    for(int i=1; i<=m; i++)
        cin>>a[i];
    sort(0,m);
//  for(int i=1;i<=m;i++)
//  cout<<a[i]<<" ";
    int p=0;
    for(int i=1; i<=m; i++) {
        if(a[i]!=a[i-1])p++;
    //  cout<<p<<endl;
        if(p==n) {
            cout<<a[p+1];
            return 0;
        }
    }
    return 0;
}

by kbzcz @ 2022-09-14 16:25:45

这题是要在快排中找,不是排完再找


by kbzcz @ 2022-09-14 16:25:53

@2115lhx


by Superficiall @ 2022-09-14 16:45:56

@2115lhx 用快排开吸氧能过

sort(x,x+n);//快排
printf("%d",x[k]);

by 2103gsc @ 2022-09-22 13:46:03

再见


|