高级数据结构-06：中位数与众数

众数

定义

给定包含 $n$ 个元素的无序向量或数组，如果某个元素的出现次数严格大于总长度一半，即出现次数 $> \lfloor n/2 \rfloor$ ，则该元素称为该向量的“众数”。这里的众数不同于统计学中“出现频率最高的数”（Mode）。例如：

在序列 {3, 5, 2, 3, 3} 中，总长度为 5。元素 3 出现了 3 次。因为出现次数 $3 > \lfloor 5/2 \rfloor = 2$ ，所以 3 是该序列的众数。
在序列 {3, 5, 2, 3, 3, 0} 中，总长度为 6。元素 3 仍出现 3 次。由于 $3$ 不严格大于 $6/2 = 3$ ，因此该向量不存在众数。

常见直接算法有两类：

全量排序结合线性扫描：先对数组排序，使相同元素连续相邻，再线性扫描并统计连续段长度。一旦某个元素计数超过 $\lfloor n/2 \rfloor$ 即可返回。该方法瓶颈在排序阶段，时间复杂度为 $\mathcal{O}(n \log n)$ ；空间复杂度取决于排序算法，例如归并排序需要 $\mathcal{O}(n)$ 辅助空间，快速排序需要 $\mathcal{O}(\log n)$ 递归栈空间。若序列存在众数，则排序后该众数必定覆盖数组中间位置，因此众数也必然是该序列的中位数。
散列表统计法：遍历数组，将元素作为键（Key）、出现次数作为值（Value）存入散列表。如果某个计数超过 $\lfloor n/2 \rfloor$ ，即可确认众数。该方法利用散列表 $\mathcal{O}(1)$ 平摊查找时间，将总体时间复杂度降至 $\mathcal{O}(n)$ ；代价是最坏情况下需要 $\mathcal{O}(n)$ 额外空间。

目标是在线性时间 $\mathcal{O}(n)$ 内完成查找，并将附加空间控制为 $\mathcal{O}(1)$ 。

Boyer-Moore 多数投票算法

Boyer-Moore 算法基于“减而治之”和“异类相消”。它只需常数级内存和一次线性遍历，即可找出潜在众数候选者。算法维护两个状态变量：

majority_candidate：用于记录当前轮次可能成为众数的候选元素。
counter：用于记录该候选元素相对其他元素的抵消余量，初始值设为 0。

算法从前向后逐一处理元素 $x$ ：

重置阶段：若 counter 为 0，说明之前的候选者已被抵消。将当前元素 $x$ 设为新的 majority_candidate，并令 counter = 1。
抵消阶段：若 counter 不为 0，则将新元素 $x$ 与当前 majority_candidate 比较：

如果它们是相同的元素，说明当前候选者得到一次额外计数，counter 递增 1。
如果它们不相同，说明当前元素与候选者互相抵消一次，counter 递减 1。

处理完整个数组后，majority_candidate 中保留的是众数候选者。若题目不保证众数存在，还需要第二次扫描验证其出现次数是否超过阈值。

counter 可以理解为当前候选者在尚未被抵消的片段中的净票数，而不是它在全数组中的真实出现次数。每遇到一个不同元素，就相当于拿一个候选者和一个非候选者配对删除。若某个元素真的超过一半，那么无论怎样配对删除，它总会在剩余序列中留下至少一个代表。

假设输入数组为 1, 2, 3, 2, 2, 2, 4, 2, 2（共 9 个元素，其中 2 出现了 6 次，因此是众数）。

下表展示了 Boyer-Moore 算法内部状态的逐元素演变过程：

遍历步骤	当前处理元素 x	执行前的 Candidate	执行前的 Counter	动作	执行后的 Candidate	执行后的 Counter
初始状态	无	None	0	系统初始化。	None	0
1	`1`	None	0	发现计数器为 0，新元素 `1` 成为新候选者，获得 1 点投票。	`1`	1
2	`2`	`1`	1	`2` 与当前候选者 `1` 不同，两者相互抵消，计数器减为 0。	`1`	0
3	`3`	`1`	0	前代候选者计数为 0，元素 `3` 成为新候选者。	`3`	1
4	`2`	`3`	1	`2` 攻击 `3`，计数器再次清零。	`3`	0
5	`2`	`3`	0	计数为 0，连续的第二个 `2` 成为全新候选者。	`2`	1
6	`2`	`2`	1	读到 `2`，投票值增加 1。	`2`	2
7	`4`	`2`	2	遇到 `4`，候选者 `2` 消耗一票。	`2`	1
8	`2`	`2`	1	候选者 `2` 再次得一票。	`2`	2
9	`2`	`2`	2	`2` 得票数最多，成为众数	`2`	3

在该推演中，元素 2 的数量超过总数一半，配对抵消后仍会保留，因此最终成为众数候选者；第二遍计数后可确认它确实是众数。

减而治之的第二遍扫描

如果在遍历某一时刻 $t$ ，计数器 counter 被减为 0，表示刚扫描过的某个偶数长度前缀 $P$ 中，阶段候选者与所有非候选元素完成了 1:1 抵消。

此时，原序列 $A$ 可分为前缀 $P$ 与后缀 $A - P$ 。若原序列 $A$ 中存在众数 $m$ ，则：

在被剔除的前缀 $P$ 中，所有元素完成两两抵消， $m$ 在 $P$ 中最多只占一半。
既然 $m$ 在全局中超过一半，而在前缀 $P$ 中至多占一半，那么在后缀 $A - P$ 中， $m$ 仍然保持多数。
因此，向量 $A$ 存在众数，当且仅当剥离前缀 $P$ 后的后缀 $A - P$ 存在同一个众数 $m$ 。

算法通过持续剥离可抵消前缀来缩小问题规模。majCandidate 函数通过 c == 0 判断当前前缀是否抵消完毕，并在后续扫描中更新 majCandidate。

需要注意，Boyer-Moore 第一遍扫描只给出必要条件：如果序列存在众数，则该众数必定是最终候选者。但如果序列本身没有众数，例如 1, 2, 3, 4, 5 中每个元素都只出现一次，算法仍会留下一个候选者；该候选者并不满足众数定义。

因此，除非题目保证输入中一定存在众数，否则必须进行第二遍扫描。第二遍扫描统计候选元素在原数组中的实际出现次数。只有当次数严格大于 $\lfloor n/2 \rfloor$ 时，才能确认众数；否则应返回空值或抛出异常。

中位数

在长度为 $n$ 的有序序列 $S$ 中，若采用从 0 开始的下标，本文将 $S[\lfloor n/2 \rfloor]$ 作为中位数；当 $n$ 为偶数时，这对应上中位数。寻找中位数本质上是寻找第 $k$ 大元素（k-selection）的特例。

先讨论一个归并排序中的常见子问题：给定两个已排序数组，如何高效找出它们合并后的全局中位数？

蛮力归并及其优化

假设系统任意给定了两个有序向量 $S_1$ 和 $S_2$ ，它们的长度分别为 $n_1$ 和 $n_2$ 。

最直接的方法是将两个有序数组按顺序合并为新的全局有序数组 $S$ ，再根据索引取 $S[(n_1 + n_2)/2]$ 附近的中间元素。该方法需要访问并搬运所有元素，时间复杂度为 $\mathcal{O}(n_1 + n_2)$ ，并需要 $\mathcal{O}(n_1 + n_2)$ 额外空间。

分治策略

要获得对数级算法，需要充分利用两个数组已有序这一条件，并采用分治策略。

先考察等长子向量情况，即 $S_1$ 和 $S_2$ 长度均为 $n$ 。直接比较两个数组各自的中位数：令 $m_1 = S_1[\lfloor n/2 \rfloor]$ ， $m_2 = S_2[\lfloor (n-1)/2 \rfloor]$ 。结果分为三种：

若 $m_1 = m_2$ ，该值同时是两个数组的局部中位数，也就是合并后的全局中位数，直接返回。
若 $m_1 < m_2$ ， $S_1$ 的前半部分只能位于合并数组较前位置，不可能成为全局中位数； $S_2$ 的后半部分只能位于较后位置，也不可能成为全局中位数。因此可以同时排除 $S_1$ 前半部分和 $S_2$ 后半部分。由于排除的较小元素与较大元素数量相等，中位数目标秩不变。
若 $m_1 > m_2$ ，将上一种情况对称处理即可。

每次截断都会使问题规模减半。每层递归只需 $\mathcal{O}(1)$ 比较，因此等长情况下时间复杂度为 $\mathcal{O}(\log n)$ 。

对于任意长度的子向量（设 $n_1 \le n_2$ ），处理边界时需要更多秩计算，但分治思想不变：

算法演进阶段	核心执行机制	峰值时间复杂度	峰值空间复杂度
蛮力完全归并法	申请新内存，完整合并后取正中间元素	$\mathcal{O}(n_1 + n_2)$	$\mathcal{O}(n_1 + n_2)$
双指针线性遍历	不分配新内存，使用双指针推演，迭代至第 $k$ 步停止	$\mathcal{O}(n_1 + n_2)$	$\mathcal{O}(1)$
二分与分治法	递归比较 $\lfloor k/2 \rfloor$ 战略点，每次贪婪抛弃一半不可能元素	$\mathcal{O}(\log(\min(n_1, n_2)))$	$\mathcal{O}(1)$

有序数组求中位数的分治，关键不是“随便丢掉一半”，而是成对丢掉同样数量的过小元素和过大元素。只要两边丢弃数量保持平衡，全局中位数的秩就不会漂移，剩下的子问题仍然是在找同一个目标秩。

K-选取

前述算法建立在数组已有序的条件上。若数组无序，要找排名第 $k$ 的元素，就得到 k-selection 问题。当 $k = \lfloor n/2 \rfloor$ 时，即为无序序列的中位数查找。

全量排序与堆排序

全量排序：对输入数组执行快速排序或归并排序，再访问下标为 $k$ 的元素。该方法时间复杂度为 $\mathcal{O}(n \log n)$ 。它能够得到目标元素，但为查找第 $k$ 个元素构造完整全序关系，计算量超过问题本身需求。

引入堆：围绕堆可以设计三种常见策略。

构建全局小顶堆：将这 $n$ 个无序元素一次性构建为一个小顶堆。这个建堆过程只需花费 $\mathcal{O}(n)$ 的线性时间。随后连续调用 $k$ 次 delMin() 弹出堆顶元素。每次弹出的结构重整代价是 $\mathcal{O}(\log n)$ ，因此总时间消耗为 $\mathcal{O}(n + k \log n)$ 。当 $k$ 很小（例如仅寻找全局最小的 3 个元素）时，这种方法较快；但一旦任务变为寻找中位数（即 $k = n/2$ ），复杂度会退化至 $\mathcal{O}(n \log n)$ 。
维持小规模大顶堆：也可以仅截取前 $k$ 个元素，将它们构建成一个大顶堆，代价为 $\mathcal{O}(k)$ 。随后遍历剩下的 $n-k$ 个元素，如果当前元素比堆顶的最大值还要小，就替换堆顶并重新执行下滤操作。全局遍历完毕后，总时间消耗为 $\mathcal{O}(k + (n-k) \log k)$ 。在寻找中位数的场景下，其复杂度依然是 $\mathcal{O}(n \log n)$ 。
双堆维护：将输入数据划分为规模为 $k$ 的大顶堆与规模为 $n-k$ 的小顶堆。随后两个堆反复比较并交换堆顶，直到大顶堆最大值小于小顶堆最小值。该模型仍难以突破全量排序的复杂度量级。

快速选择算法

每轮 QuickSelect 从当前数组中随机选择一个 pivot，并按数值大小将数组划分为三部分：

$L$ （Left）：所有严格小于 pivot 的元素。
$E$ （Equal）：所有与 pivot 完全相等的元素。
$G$ （Greater）：所有严格大于 pivot 的元素。

无论三个部分内部如何排列，pivot 已经位于全局排序后的正确秩区间。若目标秩 $k$ 落在 $E$ 对应区间，搜索结束；若 $k \le |L|$ ，只在 $L$ 中继续查找；否则在 $G$ 中继续查找并调整目标秩。

QuickSelect 每一轮只需要知道目标秩落在哪个分区。如果按从小到大的第 $k$ 小来记，且 $|L| < k \le |L|+|E|$ ，答案就是 pivot；若 $k \le |L|$ ，继续在 $L$ 中找第 $k$ 小；若落在 $G$ 中，则在 $G$ 中找第 $k-|L|-|E|$ 小。代码实现时最容易出错的地方就是这一步的秩换算。

性能期望： 若每次都能选到将数组二等分的中位数作为 pivot，问题规模按 $n, n/2, n/4, n/8...$ 衰减。由于 $\sum_{i=0}^{\infty} \frac{n}{2^i} = 2n$ ，总时间为 $\mathcal{O}(n)$ 。

QuickSelect 并不需要这种极端的幸运。我们记算法的期望比较次数为 $T(n)$ 。在随机抽取基准的情况下，每一次划分会产生 $0$ 到 $n-1$ 规模的不等分。其期望时间满足以下递推：

$T(n) = (n-1) + \frac{1}{n}\sum_{k=0}^{n-1}\max(T(k), T(n-k-1)) \le (n-1) + \frac{2}{n} \times \sum_{k=n/2}^{n-1}T(k) \le (n-1) + \frac{2}{n} \times \sum_{k=n/2}^{n-1}4k \le (n-1) + 3n < 4n$

该递推式可通过放缩和数学归纳证明 $T(n) \le 4n$ 。因此 QuickSelect 的期望时间复杂度为 $\mathcal{O}(n)$ 。

但若输入处于极端分布，例如已经正序或逆序，而算法又总是选择最大或最小元素作为 pivot，每轮花费 $\mathcal{O}(n)$ 划分后只能剔除 1 个元素，时间复杂度会退化为 $\mathcal{O}(n^2)$ 。BFPRT 用于将最坏情况稳定在线性时间。

BFPRT 算法

算法实现

BFPRT 算法的目标是避免 QuickSelect 在最坏情况下退化。它通过构造具有稳定质量的 pivot，确保每一次划分都能丢弃一个恒定比例的元素，从而保证最坏情况下的线性时间复杂度。

为了在大量元素中选出质量稳定的划分轴点，即不太接近最大值或最小值的元素，可以使用“中位数的中位数”机制。流程如下：

粗粒度切分：将 $n$ 个无序元素均匀划分为 $\lfloor n/Q \rfloor$ 个子序列。每个完整子序列包含 $Q$ 个元素。零头元素可并入最后一个不足 $Q$ 的子序列或忽略，不影响渐近边界。
局部排序：对每个子数组用常数代价插入排序，并取出其中位数。由这些中位数组成规模约为原数组 $1/Q$ 的代表集合 $T$ 。
递归自身：对代表集合 $T$ 递归调用 BFPRT，找出 $T$ 的中位数 $M$ 。这个 $M$ 就是“中位数的中位数”。
划分：算法像 QuickSelect 那样，将 $M$ 作为 pivot，在原数组中进行扫描。将原数组分为三个部分： $L$ 、 $E$ 、 $G$ 。
在子区间递归：最后，算法根据 $k$ ，判断它所在的区段（比较 $k$ 与 $|L|$ 以及 $|L|+|E|$ 的关系），在相应的、规模已经缩减后的子区间中继续搜索。

BFPRT 的核心是用额外的线性工作换来“足够不坏”的轴点，而不是一定找出真正的全局中位数。分组大小通常取 5，是因为它既能保证每组中位数提供足够的淘汰比例，又不会让组内排序和递归常数过大。只要每轮能稳定丢弃一个固定比例的元素，最坏情况就能保持线性。

步骤 3 得到的 $M$ ，在最坏情况下也不会过于接近最大或最小值。第 2 步建立了约 $n/Q$ 个小组；第 3 步中， $M$ 是这些组中位数的中位数。因此，在中位数组成的集合 $T$ 中，有一半小于或等于 $M$ 。换言之，至少有 $\frac{1}{2} \times \frac{n}{Q} = \frac{n}{2Q}$ 个原数组子数组，其组中位数小于或等于 $M$ 。

考虑这 $\frac{n}{2Q}$ 个子数组。对于其中任意一个，既然其组中位数 $\le M$ ，那么该组中位数及其左侧的 $\lfloor Q/2 \rfloor$ 个元素也都 $\le M$ 。因此，每个这样的完整小组至少提供 $\lfloor Q/2 \rfloor + 1$ 个不大于 $M$ 的元素。若采用 BFPRT 常用的 $Q=5$ ，则每组至少提供 3 个元素。因此，原序列中小于等于 $M$ 的元素总数下限至少为：

$3 \times \frac{n}{2Q} = \frac{3n}{2Q}$

这意味着步骤 4 划分时，小于等于 $M$ 的元素数量至少占总数的 $\frac{3}{2Q}$ 。同理，大于等于 $M$ 的元素数量也至少达到 $\frac{3}{2Q}$ 。当 $Q=5$ 时，每轮至少能在一侧排除约 $3n/10$ 个元素，从而避免退化到 $\mathcal{O}(n^2)$ 。