60分求助,前两个点TLE

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

NGUforever @ 2021-01-31 11:55:07

#include <stdio.h>
#include <stdlib.h>

int num[5000000];
void findNum(int k,int a,int b);
int main()
{
    int n,k,i;
    i=0;

    scanf("%d %d",&n,&k);
    while (i<n)
    {
        scanf("%d",&num[i]);
        i=i+1;
    }
    findNum(k,0,n-1);
    printf("%d",num[k]);

    return 0;
}

void findNum(int k,int a,int b)
{
    int mid,l,r,tool;
    l=a;
    r=b;
    mid=num[(a+b)/2];
    while (l<r)
    {
        while (num[l]<mid)
        {
            l=l+1;
        }
        while (num[r]>mid)
        {
            r=r-1;
        }
        if (l<r)
        {
            tool=num[r];
            num[r]=num[l];
            num[l]=tool;
        }
    }
    if (l-a>1&&(k>=a&&k<=l))
        findNum(k,a,l);
    else if (l-a==1)
    {
        if (num[l]<num[a])
        {
            tool=num[a];
            num[a]=num[l];
            num[l]=tool;
        }
    }
    if (b-r>1&&(k>=r&&k<=b))
        findNum(k,r,b);
    else if (b-r==1)
    {
        if (num[b]<num[r])
        {
            tool=num[b];
            num[b]=num[r];
            num[r]=tool;
        }
    }
}

代码写的有点乱,大体思路就是把需要排序的地方快排,不需要排序的就不理他,求求大佬帮忙看看哪里出了问题,或者怎么才能更好的优化


by NGUforever @ 2021-01-31 12:38:13

我找到TLE的原因了

if (l<r)
        {
            tool=num[r];
            num[r]=num[l];
            num[l]=tool;
            r=r-1;
            l=l+1;
        }

在这里加上r=r-1;l=l+1就可以了,不加的话遇上重复数据会进入死循环。


|