众数

· · 算法·理论

随机法求绝对众数

因为绝对众数的出现次数 >\frac{n}{2}，所以如果存在绝对众数，则从序列中随机抽取一个数是众数的概率超过 50\%。

所以我们抽取 C 分别检查出现次数是否 >\frac{n}{2}，如果找到则返回众数，如果找完了 C 个数还没有众数则返回无众数。找不到绝对众数的概率 <\frac{1}{2^C}，因为一般都为多次查询而且可能重复抽取相同数字，所以通常保守取 C = 50。

可以考虑把序列进行离散化，然后定义 n 个 vector v_i 从小到大存所有值为 i 的下标位置。查询权值 c 是否为 a_{[l, r]} 的绝对众数，可以在 v_c 中二分找到满足 v_{c, u}\ge l 的最小 u，然后在 v_c 中二分找到满足 v_{c, w}\le r 的最大 w，那么 c 在 a_{[l, r]} 的出现次数就是 w - u + 1。

所以一次查询 [l, r] 子序列众数的复杂度为 C\log n，注意算法是有极小概率出错的。

求众数出现次数

设 \text{mc}_{l, r} 表示 a_{[l, r]} 的众数出现次数，设 \text{cnt}_{v, l, r} 表示 v 在 a_{[l, r]} 的出现次数，则有性质 \text{mc}_{l, r} = \max(\text{mc}_{l, r - 1}, \text{cnt}_{a_r, l, r})，进而拓展得到 \text{mc}_{l, r} = \max(\text{mc}_{l, f - 1},~\max_{j = f}^r \text{cnt}_{a_j, l, r})。

以 B 为块长序列分块，则预处理 \text{pre}_{l, r} 表示第 l\sim r 块构成的区间的众数出现次数，预处理复杂度 \frac{n^2}{B}\log n，每次查询找到查询区间包含的最大整块区间再向外拓展，复杂度 nB\log n，均衡得总复杂度 \mathcal {O}(n\sqrt n\log n)。

预处理 \text{pum}_{i, v} 表示值 v 在前 i 块的出现次数，预处理 \text{cot}_{i} 表示 a_i 在 [L_{\text{bel}_i}, i] 的出现次数，可以做到 \mathcal O(1) 扩展，进而总复杂度 n\sqrt n。

离线求众数及出现次数

对询问做莫队，维护出现次数为 k 的值的个数，以及出现次数最多的值的个数 \text{mxt} 及具体数值，复杂度 n\sqrt n。

二进制拆位法求绝对众数

需要保证存在绝对众数才可使用，优势是支持快速插入、删除、合并，而且错误的概率是 0。

对于序列 a，维护 \text{cnt}[32] 表示 a 中有多少个数在该位是 1，那么绝对众数对应为 1 的位 \text{cnt}[i] 一定为 1，绝对众数对应位 0 的位 \text{cnt}[i] 一定为 0。

找出有 \text{cnt}[i] > \frac{n}{2} 的位组成的数就是绝对众数。

插入 x 时在 x 的对应二进制为 1 的位使 \text{cnt}[i] 增加 1，删除同理。合并时将两个 \text{cnt} 数组对应位置相加即可。这些操作复杂度都为 \log V。

习题

P8496 [NOI2022] 众数

P4168 [Violet] 蒲公英

P13984 数列分块入门 9

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III