虽然用另一种写法AC了，但还是想问下

jor蛋 @ 2021-08-07 14:55:04

#include<stdio.h>
int a[100000010];
int quick_sort(int q[],int l,int r){
    if(l>=r)    return 0;
    int i=l-1, j=r+1, x=q[(l+r)/2];
    while(i<j){
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j){
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
        }
    }
    quick_sort(a,l,j);  quick_sort(a,j+1,r);
}
int main(){
    int n,m,i,sum=0,k;
    scanf("%d%d",&m,&k);
    for(i=1;i<=m;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,m);
    k=k+1;
    for(i=1;i<=m;i++){
        if(a[i]!=a[i-1]){
            sum++;
        }
        //  printf("%d\n",sum);
        if(sum==k){
            printf("%d\n",a[i]);
            break;
        }

    }       
}

by jor蛋 @ 2021-08-07 15:15:37

@2simon2008 改了还是WA

by vectorli1 @ 2021-08-07 15:16:25

主程序里还要加上一句 srand(int(time(0))); 头文件还需要 include<time.h>

by jor蛋 @ 2021-08-07 15:16:45

@VecTorLi C语言怎么写啊。应该不能直接return吧

by vectorli1 @ 2021-08-07 15:18:35

您稍等，我帮您调一下

by vectorli1 @ 2021-08-07 15:24:26

调好了，可以得到一些分数，但是这个算法的时间复杂度是 O(n\log n) ，不是正解。

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int a[5000000 + 5];
//int quick_sort(int q[],int l,int r){
  void quick_sort(int q[],int l,int r){
    //if(l>=r)    return 0;
      if(l>=r)    return;
    //int i=l-1, j=r+1, x=q[(l+r)/2];
    int i=l, j=r, x=q[rand()%(r-l+1)+l];
    //while(i<j){
    while(i<=j){
        while(q[i]<x) i++;
        while(q[j]>x) j--;
        //if(i<j){
        if(i<=j)
        {
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
            i++;j--;
        }
    }
    //quick_sort(a,l,j);
    //quick_sort(a,j+1,r);
    quick_sort(q, l, j);
    quick_sort(q, i, r);
}
int main(){
    srand(int(time(0)));
    int n, k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    printf("%d\n", a[k+1]);
    return 0;  
}

by vectorli1 @ 2021-08-07 15:26:00

发错了，是

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int a[5000000 + 5];
//int quick_sort(int q[],int l,int r){
  void quick_sort(int q[],int l,int r){
    //if(l>=r)    return 0;
      if(l>=r)    return;
    //int i=l-1, j=r+1, x=q[(l+r)/2];
    int i=l, j=r, x=q[rand()%(r-l+1)+l];
    //while(i<j){
    while(i<=j){
        while(q[i]<x) i++;
        while(q[j]>x) j--;
        //if(i<j){
        if(i<=j)
        {
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
            i++;j--;
        }
    }
    //quick_sort(a,l,j);
    //quick_sort(a,j+1,r);
    quick_sort(q, l, j);
    quick_sort(q, i, r);
}
int main(){
    srand((time(0)));
    int n, k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    printf("%d\n", a[k+1]);
    return 0;  
}

by jor蛋 @ 2021-08-07 15:38:55

@VecTorLi 我还是想问下先排全部排好然后再输出第k+1个不重复的数为什么不行。

by 2simon2008 @ 2021-08-07 15:50:49

@jor蛋 快排的时间复杂度是nlogn，这里n < 5000000,约为10^{10} ，显然TLE。

by jor蛋 @ 2021-08-07 16:16:02

@2simon2008 我是WA喂，而且我一个点都没过，讲道理不应该啊，是吧

by vectorli1 @ 2021-08-07 16:30:34

不是输出第 k+1 个不重复的数，是输出第 k+1 个数，您审错题了