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就可以了,不加的话遇上重复数据会进入死循环。