[//]: # 6_17号 打卡
题目描述
blablabla
样例
blablabla
C++ 代码
#include <iostream>
using namespace std;
const int N = 10000005;
int a[N];
int partition(int a[], int left, int right)
{
int l = left;
int r = right;
int key = a[right];
while(l < r)
{
while(l < r && a[l] <= key)
l++;
while(l < r && a[r] >= key)
r--;
swap(a[l],a[r]);
}
swap(a[right],a[l]);
return l;
}
/*
int partition(int a[], int left, int right)
{
int small = left - 1;
for(int index = left; index < right; index++)
{
if(a[index] < a[right])
{
++small;
if(small != index)
swap(a[small],a[index]);
}
}
++small;
swap(a[small],a[right]);
return small;
}
*/
int kthNumbers(int a[], int n, int k)
{
int left = 0;
int right = n - 1;
int mid = partition(a,0,n-1);
while(mid != k - 1)
{
if(mid < k - 1)
{
left = mid + 1;
mid = partition(a,left,right);
}
else if(mid > k - 1)
{
right = mid - 1;
mid = partition(a,left,right);
}
else
break;
}
return a[mid];
}
int main()
{
int n = 0;
int k = 0;
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
printf("%d\n", kthNumbers(a,n,k));
return 0;
}