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

题目描述

输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

题解

#include <bits/stdc++.h>
using namespace std;

int n, k, a[5000010], ans;

void findk(int a[], int l, int r) {
	if (l == r) {
		ans = a[r];
		return;
	}
	int i = l, j = r, flg = a[(l + r) / 2], t;
	do {
		while (a[i] < flg)
			i++;
		while (a[j] > flg)
			j--;
		if (i <= j) {
			swap(a[i], a[j]);
			i++;
			j--;
		}
	} while (i <= j);
	if (k <= j)
		findk(a, l, j);
	else if (i <= k)
		findk(a, i, r);
	else
		findk(a, j + 1, i - 1);
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	//sort(a, a + n);
	findk(a, 0, n - 1);
	cout << ans;
	return 0;
}