主元素法

问题引入

已知一个序列 \(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。