线性时间选择

线性时间选择

在线性时间内求出数组中第 $k$ 小的元素。

该问题可以通过分治来解决:

  • 随机选择数组中的一个元素,把小于它的元素放在它的左边,大于它的元素放在右边(相等的放在左右都可以,尽量保证两边的数量差不多,不然对于数字全相等的情况可能会退化)。
  • 判断递归左边或右边。

可以证明这样期望的复杂度是 $O(n)$ 的。

nth_element() 是线性时间选择在标准库中的实现。

我按照同样的接口简单实现了一下。

一道模板题:hdu 6040

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 0-index, O(n)
struct Nth_element {
mt19937 rnd;
int a[maxn];

Nth_element() : rnd(time(0)) {}

int RandomizedPartition(int l, int r) {
uniform_int_distribution<int> distribution(l, r); // 均匀分布
int pos = distribution(rnd); // 随机选择
swap(a[l], a[pos]);

int L = l + 1, R = r;
int val = a[l];
while (true) {
while (L < r && a[L] < val) L++;
while (l < R && a[R] > val) R--;
if (L >= R) break;
swap(a[L], a[R]);
L++, R--;
}
a[l] = a[R];
a[R] = val;
return R;
}
// [l+1,k]的元素都小于等于a[k],[k+1,r]的元素都大于等于a[k]。
void RandomizedSelect(int l, int r, int k) {
if (r - l + 1 <= k) assert(false);
if (l == r) return;
int pos = RandomizedPartition(l, r);
if (pos - l == k)
return;
else if (pos - l > k)
RandomizedSelect(l, pos - 1, k);
else
RandomizedSelect(pos + 1, r, k - (pos - l + 1));
}
};