时间复杂度: $O(n)$
C++ 代码
#include <iostream>
using namespace std;
const int MAX = 1e5 + 10;
int a[MAX];
int partition(int a[], int l, int r) {
// lomuto版分割法
int m = l;
int p = a[l];
for (int i = l + 1; i <= r; ++i) {
if (a[i] <= p && ++m != i)
swap(a[i], a[m]);
}
swap(a[l], a[m]);
return m;
}
void find_k(int a[], int l, int r, int k) {
if (l >= r) return;
int m = partition(a, l, r);
// 这时 [l, m] <= p, [m+1, r] > p
if (m > k)
find_k(a, l, m - 1, k);
else if (m < k)
find_k(a, m + 1, r, k);
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
// 第k个数的index是k-1
find_k(a, 0, n - 1, k - 1);
cout << a[k - 1] << endl;
return 0;
}