Zzy20060323 @ 2024-09-21 00:13:56
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int n, k;
int a[5000001], b[5000001], c[5000001], d[5000001];
void px(int s, int l)
{
if (s >= l)
{
return;
}
int mid = rand() % (l - s) + s;
int tb = 0, tc = 0, td = 0;
for (int i = s; i < l; i++)
{
if (a[i] < a[mid])
{
b[++tb] = a[i];
}
else if (a[i] > a[mid])
{
c[++tc] = a[i];
}
else
{
d[++td] = a[i];
}
}
for (int i = 1; i <= tb; i++)
{
a[s + i - 1] = b[i];
}
for (int i = 1; i <= td; i++)
{
a[s + tb + i - 1] = d[i];
}
for (int i = 1; i <= tc; i++)
{
a[s + tb +td + i - 1] = c[i];
}
px(s, tb+s);
px(tb + td + s, l);
}
int main()
{
srand((unsigned int)time(0));
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
px(0, n);
printf("%d", a[k]);
return;
}
by lizechenQAQ @ 2024-09-21 05:35:40
@Zzy20060323 sort是个好东西
by Zzy20060323 @ 2024-09-21 07:35:33
大佬能告诉我这为什么不行吗
by __owowow__ @ 2024-09-21 08:03:26
@Zzy20060323 其实快排代码更短,还更快。建议这道题用快排
by __owowow__ @ 2024-09-21 08:04:37
@Zzy20060323 而且这道题 nlogn过不了的