线性时间选择

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

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

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

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

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

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

一道模板题:hdu 6040

// 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));
  }
};
最后修改:2020 年 07 月 30 日 10 : 19 PM