RE求助

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

wangzaixi @ 2024-09-07 18:22:32

#include<iostream>
using namespace std;
void countSort(int array[],int n){
    int max=array[0],min=array[0];
    for(int i=1;i<n;i++){
        if(array[i]>max){
            max=array[i];
        }
        if(array[i]<min){
            min=array[i];
        }
    }
    int countArray[max-min+1]={0};
    for(int i=0;i<n;i++){
        countArray[array[i]-min]++;
    }
    int index=0;
    for(int i=0;i<max-min+1;i++){
        for(int j=0;j<countArray[i];j++){
            array[index]=i+min;
            index++;
        }
    }
}
int main(){
    int a[1000],n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    countSort(a,n);
    cout<<a[m];
    return 0;
}

by Finner_forgeter @ 2024-09-07 18:29:50

数组太小sir @wangzaixi

by THE_SUPER_WING @ 2024-09-12 20:25:47

超短AC代码

#include<bits/stdc++.h>

using namespace std;

int x[5000005], k;
int main()
{
    int n;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    nth_element(x, x + k, x + n);
    cout << x[k];
}

by ZHAOJJzjj123 @ 2024-09-17 13:15:41

@THE_SUPER_WING 我也这么写的，可以过！

by wangzaixi @ 2024-09-24 21:43:14

@THE_SUPER_WING 卡了好久，终于过了

#include<bits/stdc++.h>
using namespace std;
int n,k,a[5000000];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    cout<<a[k];
    return 0;
}