AcWing 786. 求第k个数O(N)
原题链接
简单
作者:
qiao
,
2022-09-23 12:15:34
,
所有人可见
,
阅读 165
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
//O(N)
int quick_search(int a[], int l, int r, int k)
{
if (l == r) return a[r];
int i = l - 1, j = r + 1, x = a[rand() % (r - l + 1) + l];//防止最坏情况
while (i < j)
{
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j)swap(a[i], a[j]);
}
int p = j - l + 1;//p:集合划分后的分界点[1,j][j+1,r]
if (k <= p)return quick_search(a, l, j, k);//在[1,j]
else return quick_search(a, j + 1, r, k - p);//在[j+1,r]
}
int main()
{
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
cout<<quick_search(a, 1, n, k);
}