摩尔投票法(Boyer-Moore majority vote algorithm)可以解决绝对众数问题及相关问题。

定义

绝对众数:长度为 $n$ 的数列中出现次数严格大于 $\left\lfloor\frac{n}{2}\right\rfloor$ 的数。

「$\frac{1}{k}$ 众数」:长度 $n$ 的数列中出现次数严格大于 $\left\lfloor\frac{n}{k}\right\rfloor$ 的数。特殊地,当 $k = 2$ 时「$\frac{1}{2}$ 众数」即为绝对众数。


基本原理

摩尔投票法:对于一个长度为 $n$ 的数列 $\{a_{i}\}$,每次选出两个不同的元素并删除,直到无法删除为止。如果此时数列为空,则原数列不存在绝对众数,否则原数列的绝对众数为剩下的数(这些数字一定相同)。


例题

「BZOJ 2456」mode

求全局的绝对众数,保证存在。

空间限制 $1 \texttt{MB}$。

记录当前剩余数字 $num$ 和剩余个数 $cnt$。对于新的一个数字 $x$:

  • 存在剩余数字即 $cnt > 0$ 时,

    • 如果 $x = num$,则 $cnt \leftarrow cnt + 1$;
    • 否则,则将一个 $num$ 和 $x$ 删去 $cnt \leftarrow cnt - 1$。
  • $cnt = 0$ 时,说明之前的部分不存在绝对众数,那么这个众数一定在剩余部分中为绝对众数,重新回到了原问题,$num \leftarrow x, cnt \leftarrow 1$。

「Codeforces 674G」Choosing Ads

求区间出现频率不小于 $p \%$ 的数。

$20 \le p \le 100$。

将摩尔投票法扩展一下,每次删除 $k$ 个不同的数,就能够求解「$\frac{1}{k}$ 众数」了。

又发现这个过程是有可合并性的,用线段树维护这个过程即可。

区间合并的复杂度为 $\mathcal O(k^{2})$,由于 $k_{\max} = \frac{100}{p} = 5$,复杂度接近常数因此可以暴力合并。

最后修改:2021 年 04 月 28 日 11 : 09 AM