一直60分,前三个点过了,后两个一直TLE
#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;
}