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

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

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 16:33:34

@VecTorLi 不是喂,他说输出第k小的数, 那同一数字重复多少次不是表示同一小的数啊,所以重复的数字要算成一个数字喂。难道不是这样的吗


by vectorli1 @ 2021-08-07 16:35:32

您可以看一下第二篇题解


by vectorli1 @ 2021-08-07 16:36:14

这个代码可以拿60分

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
    int n;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&x[i]);
    sort(x,x+n);//快排
    printf("%d",x[k]);
}

by jor蛋 @ 2021-08-07 16:44:19

@VecTorLi 我靠,太阴了,重复数字竟然不需要合为一个数字,晕。我试了下就T了最后一个,ok了,我说怎么回事。谢谢你


by Harry212 @ 2022-08-04 08:13:31

oct:337522 dec:??????


上一页 |