@[flowercode](/user/1236674)
首先没必要把所有数组重排,这样很费时间,而且也没必要,因为你只需要求到第 $k$ 个数,剩下的排序就是无用功。
其次你递归的终止条件有些问题,这个我稍微修改了些。
```cpp
#include<iostream>
using namespace std;
int n, arr[5000005];
int part(int start, int end, int pi) {
int pv = arr[pi];
swap(arr[pi], arr[end]);
int i = start;
for (int j = start; j < end; j++) {
if (arr[j] < pv) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[end]);
return i;
}
void qs(int start, int end, int k) {
if (start == end) return;
int pi = (start + end) / 2;
pi = part(start, end, pi);
if (k < pi) qs(start, pi - 1, k);
else if (k > pi) qs(pi + 1, end, k);
}
int main() {
int m, k;
scanf("%d%d", &m, &n);
for (int i = 0; i < m; ++i) {
scanf("%d", &arr[i]);
}
qs(0, m - 1, n);
printf("%d", arr[n]);
return 0;
}
```
by Zemu_Ooo @ 2024-03-29 03:55:01
@[Zemu_Ooo](/user/467824) 谢谢大佬!!!
by flowercode @ 2024-04-03 21:17:47