算法基础算法

快速选择算法

字数统计: 1.2k字   |   阅读时长: 4分

背景

快速选择算法是解决【从 N 个元素中选出前 K 个或第 K 个】这个问题的算法。这个问题是 topK 问题中比较简单的一类，稍微复杂一点的 topK 问题就需要用堆和值域二分等算法。关于 TopK 问题，可以参考这篇文章: topK问题分类汇总

快速选择算法是一种减治算法，通过 partition 将问题区间 [left, right] 划分为 [left, partition] 和 [partition + 1, right]，然后解决其中一个子问题即可得到原问题的解。关于减治算法，在文章 减治法 中总结了常见的问题和题目列表。减治法与分治法很容易混淆，在文章 分治 中，总结了关于分治的常见问题。分治和减治的具体区别主要是划分出子问题后，要解决的子问题数量不同，减治法只解决一个子问题即可得到答案，而分治法需要解决两个及以上子问题才可得到答案，在维基百科关于 Divide and Conquer 中也有相关论述

Sone authors consider that the name “divide and conquer” should be used only when each problem may generate two or more subproblems
The name decreace and conquer has been proposed instead for the single-subproblem class

在快速选择算法中，划分 partition 进而转化为子问题的思路与快排中的划分方式完全相同。在文章 数组排序 中有关于快排的实现。

如果按照该划分 partition 的思路把子问题的结果组织成树形结果保存下来共后续查询，就会得到划分树(与归并树类似，归并树保存的是归并排序的子问题结果)，在文章 力扣215-快速选择算法,划分树 中用多种方法解决了 TopK 问题，并实现了划分树。

快速选择算法

考虑在子区间 [left, right] 中选择第 k 大的数这个问题

首先按照快排中划分子问题的方法对当前问题做同样的子问题划分，也就是一轮的划分做下面这两件事

  1. 选择一个枢轴(pivot)，然后将该元素与当前的 left 位置元素交换
1
2
int randIdx = rand() % (right - left + 1) + left; // 随机选择 pivot
swap(nums[randIdx], nums[left]);
  1. 确定 pivot 位置

考查 [left, right] 上的每个元素，大于 pivot 的元素移到左边，小于等于 pivot 的元素移到右边。

1
2
3
4
5
6
7
int pivot = nums[left];
int l = left, r = right;
while(l < r)
{
    //...
}
// 一轮 partition 完成

一轮 partition 完成后，pivot 的位置为 l，此时考察 l 和 left + K 的关系，[left, right] 中第 K 个位置的下标是 left + K - 1：

1
2
3
l = left + K - 1: pivot 刚好在 [left, right] 第 k 个位置，找到答案了
l > left + K - 1: [left, l] 中有 l - left + 1 个数字，还要在 [l + 1, right] 中找 K - (l - left + 1) 个
l < left + K - 1: 在 [left, l - 1] 中继续找第 k 大

时间复杂度平均 $O(N)$，最坏 $O(N^{2})$，但是最坏情况太难达到了，一般还是认为快速选择算法是 O(N) 的。

快速选择算法有一个优化：BFPRT算法，也叫中位数的中位数算法，它进一步优化了 pivot 的选取方法，使得最坏时间复杂度也变为 $O(N)$，它由Blum、Floyd、Pratt、Rivest、Tarjan提出。

快速选择算法每完成一轮 partition 将数据分成不均匀的两份后，只有其中一份对结果有影响，可以去掉一部分，数据规模就减少一部分，所以也叫减治算法。插入排序，DFS, BFS, 拓扑排序也隐含了减治的思想：每完成一轮，下一轮就可以少考虑一个数据。

代码(模板)

在 [left, right] 上找到第 k 大的元素，也就是从大到小排序后的第 k 个元素。

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
int partition(vector<int>& nums, int k, int left, int right)
{
    // 在 nums 的 [left .. right] 中找第 k 大
    int randIdx = rand() % (right - left + 1) + left; // 随机选择 pivot
    swap(nums[randIdx], nums[left]);
    int pivot = nums[left];
    int l = left, r = right;
    while(l < r)
    {
        while(l < r && nums[r] <= pivot)
            --r;
        if(l < r)
        {
            nums[l] = nums[r];
            ++l;
        }
        while(l < r && nums[l] > pivot)
            ++l;
        if(l < r)
        {
            nums[r] = nums[l];
            --r;
        }
    }
    nums[l] = pivot;
    if(l == left + k - 1)
        return nums[l];
    else if(l < left + k - 1)
        return partition(nums, k - (l - left + 1), l + 1, right);
    else
        return partition(nums, k, left, l - 1);
}

题目

215. 数组中的第K个最大元素

题解: 力扣215-快速选择算法,划分树

169. 多数元素

题解: 力扣169,299-摩尔投票

137. 只出现一次的数字 II

题解: 力扣136,137,260-数字出现次数

Share