主元素法

问题引入

已知一个序列 \(a_n\) 中有一个数的出现次数严格大于 \(\frac{n}{2}\) ，求这个数。

注意内存有限制，不能把所有数都存下来。

主元素做法

主元素算法基于一个事实：在具有上述性质的序列中任意选择两个不同的数删去，剩下的序列中众数仍然不变。

既然这样，我们就先假设 \(a_1\) 是答案，然后一个一个读入，记录一个 cnt = 1 ，如果读入和 \(a_1\) 相同，则 cnt++ ，否则 cnt-- 。接下来是重点：

• 如果 cnt 到最后都大于0，显然答案就是 \(a_1\) 。这没什么问题。
• 如果 cnt 在中间变成了0，那么立即将下一个数设为新的主元素，继续算法。

为什么要这样做呢？如果在 \(a_k\) 的时候 cnt 变成了0，说明前 \(k\) 个数中有 \(\frac{k}{2}\) 个数等于 \(a_1\) ，还有 \(\frac{k}{2}\) 个数不等于 \(a_1\) 。那么根据之前说的事实，我们可以一个 \(a_1\) 一个非 \(a_1\) 统统删掉，把问题规模缩小为 \(n-k\) 的新问题，自然可以再假设一个主元素 。

由于众数个数严格大于 \(\frac{n}{2}\) ，所以读完 \(a_n\) 之后 cnt 一定大于0。

问题变形

如果不是严格大于 \(\frac{n}{2}\) ，而是大于等于 \(\frac{n}{2}\) ，怎么办呢？

主元素算法是无法解决等于 \(\frac{n}{2}\) 的情况的。那么让我们看一些神奇算法。

利用评测机制漏洞

虽然内存里存不下数据，但是我们知道，数据一直存在文件里呢！

利用库函数，可以把输入流回退到开头。那就很简单了。

随机一个位置，先把这个位置读出来 然后回退到开头，全读一遍，求出这个数的出现次数。如果不够，就回退到开头，再随机一个数。

因为答案的出现次数大于等于 \(\frac{n}{2}\) ，所以随机到的概率是很大的。

利用哈希

选取三个质数，将每个数分别对这三个质数哈希的结果统计出现次数，对于三个哈希结果中都是众数的数，就可以视为是答案。

二进制拆分

这是正儿八经的正解。将每个数进行二进制拆分，记录每一位的1的出现次数，以及有几个不同的数贡献了这么多1。对于每个位单独考虑：

• 如果这一位上1的个数大于 \(\frac{n}{2}\) ，那么答案的这一位就是1。
• 如果这一位上1的个数小于 \(\frac{n}{2}\) ，那么答案的这一位就是0。
• 如果这一位上1的个数等于 \(\frac{n}{2}\) ，那么如果有不止一个数贡献了这个1，说明答案这一位是0，否则这一位就是1。