有点懵逼

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

zuilp @ 2023-12-27 19:38:46

本来以为这题会出现重复数据的,就再块排完之后数清重复数据再输出 代码如下

#include<stdio.h>
void kp(int* arr,int a,int b)
{
    if(b<=a)
    return ;
    int key=arr[(a+b)/2],i=a,big=b;
    arr[(a+b)/2]=arr[a];
while(a<b)
{
    while(arr[b]>key&&a<b)
        b--;
        if(a<b)
        arr[a]=arr[b];
    while(arr[a]<=key&&a<b)
        a++;
        if(a<b)
        arr[b]=arr[a];
}
arr[a]=key;
kp(arr,i,a-1);
kp(arr,a+1,big);
}
int main()
{
    int n,n1,k;
    scanf("%d %d",&n,&k);
    int i;
    int arr[n];
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    kp(arr,0,n-1);
        for(i=0;i<n;i++)
    {
        if(k==0)
{
printf("%d",arr[i]);
break;
}
        if(k!=0&&arr[i]!=arr[i+1])
        k--;
    }
    return 0;
}

全报错了,结果一看题解。没人考虑重复的问题,于是我就直接快排完输出arr[k];然后。。。。。就过了。这题也没给测试点。有没有大佬告诉我第一个代码哪里出问题了


by lcy666666 @ 2023-12-27 19:48:15

有没有这个第k小包含重复的数。。。


by ShiRoZeTsu @ 2023-12-27 20:41:21

@zuilp 你这个代码相当于是把相同的数字算成一个了,这道题应该没让去重。其次就是这题直接 sort 再吸氧就过了()

还有就是你的马蜂好毒瘤啊(指大括号

所以我也来水一下这道题 doge

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 5e6 + 5;

int n, k;
int a[maxn];

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    printf("%d\n", a[k]);
    return 0;
}

|