mazel @ 2023-08-02 16:32:57
#include<iostream>
using namespace std;
int a[5000005] = { 0 };
int k = 0;
void swap(int& a, int& b)
{
int c = a;
a = b;
b = c;
}
int quick_find( int l, int len) // l代表起始位置,len代表终止位置
{
if (l >= len)
return a[l];
int mid = a[rand() % (len - l) + l];
int ak = len, j = l, i = l; //ak代表大于mid的值(k--),j代表小于min的值
while (i < ak)
{
if (a[i] < mid)
swap(a[i++], a[j++]);
else if (a[i] > mid)
swap(a[i], a[--ak]);
else
i++;
}
//判断ak与j的大小判断在前半段还是后半段
if (k < j)
{
return quick_find(l , j);
}
else if (k >= ak)
{
return quick_find(ak, len);
}
else
return mid;
}
int main()
{
int n = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << quick_find(0, n) << endl;
}
by __DIOsama__ @ 2023-08-02 16:38:49
建议加个std::ios::sync_with_stdio(false)
by __DIOsama__ @ 2023-08-02 16:40:02
@mazel
by mazel @ 2023-08-02 22:02:08
@DIO__ 请问是加在哪个位置呢
by __DIOsama__ @ 2023-08-03 08:20:55
@mazel
int main()
{
std::ios::sync_with_stdio(false);
int n = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << quick_find(0, n) << endl;
}
by mazel @ 2023-08-03 12:37:52
@DIO__ 谢谢大佬,这样写就可以使cin和scanf的读入速度一样了是吧,我发现把cin全部改成scanf输入也可以加快速度,这两种方法都不会超时,感谢。