洛谷|P1923 【深基9.例4】求第 k 小的数算法|c++

题目描述输入 nn（1 \le n < 50000001≤n<5000000 且 nn 为奇数）个数字 a_iai?（1 \le a_i < {10}^91≤ai?<109），输出这些数字的第 kk 小的数。最小的数是第 00 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式无
输出格式无
输入输出样例输入 #1复制

5 1 4 3 2 1 5

输出 #1复制

2

#include using namespace std; long long n[1000000]; int k; void qswap(int b, int e) { int i = b, j = e; int num = n[(b + e) / 2]; while (i <= j) { while (n[i] < num) i++; while (n[j] > num) j--; if (i <= j) { swap(n[i], n[j]); i++; j--; } } if (k <= j) qswap(b, j); else if (k >= i) qswap(i, e); else cout << n[j + 1]; }int main() { int x; cin >> x >> k; for (int i = 0; i < x; i++) { cin >> n[i]; } qswap(0, x - 1); return 0; }

【洛谷|P1923 【深基9.例4】求第 k 小的数】