c,80分,qsort,最后一个超时了,可是不知道怎样才能不超时

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

RAN111 @ 2023-12-29 16:40:56

#include<stdio.h>
#include<stdlib.h>
int cmp(void *a,void *b)
{
    int x,y;
    x=*(int *)a;
    y=*(int *)b;
    return x-y;
}
int main(void)
{
    int n,k;
    scanf("%d%d",&n,&k);
    int a[n];
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    qsort(a,n,sizeof(*a),cmp);
    printf("%d",a[k]);
    return 0;
}

by jr_zch @ 2023-12-29 17:30:54

qsort本来就过不了,正确做法是分治O(n)


by RAN111 @ 2023-12-30 09:35:32

@jr_zch 啊好吧


by jinxiyou @ 2023-12-30 15:24:03

你可以用nth_element,这样也可以过,不回的话从网上搜


by hello141219 @ 2024-01-03 11:21:26

用分治


by sulingfeng @ 2024-01-16 18:41:47

sort不行吗?


|