摩尔投票法及其扩展

摩尔投票法是用来解决以下问题的一类方法。

Q : 在一个长度为 \(n\) 的数组中找出出现次数大于一半的元素。

很明显，利用开桶，排序找中位数等多种多样的方法都可以轻松解决，但摩尔投票法厉害之处在于它的空间复杂度仅为 \(O(1)\)，意味着数组都不用开。

摩尔投票法的核心如下：

for (int i = 1; i <= n; i++) {
	if (!cnt) ans = read(), cnt = 1;
   	else cnt += read() == ans ? 1 : -1;
}

我们可以借助文字来帮助理解上面这段话：

摩尔投票法本质上是每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

所以，\(cnt\) 存储的是当前暂时无法删除的数字的个数，表现为和上一个记录的数字相等，所以当 \(ans=read()\) 时 \(cnt\) 自增，反之自减，而 \(cnt=0\) 的意思就是"没有数字无法删除了"，即能删的都删完了，或者说没有数可以用来抵消了，只能拿当前的数放到 \(ans\) 中和后面的数抵消了。

所以我们要做的仅仅就是每次拿读入的数字和 \(ans\) 去抵消而已。

---

扩展相关

Q : 在一个长度为n的数组中找出出现次数大于 \(\left \lfloor\dfrac nk \right \rfloor\) 的元素。

为方便理解，先讨论 \(k=3\) 时的情况：

如果理解了上面 \(k=2\) 的那一段话，那么我们发现摩尔投票法是基于这样一个原理：如果一个数组里有一元素超过 \(\frac {\ 1\ }{2}\)，那么同时删除 \(2\) 个不同的数，数量超过 \(\frac {\ 1\ }{2}\) 的数仍然超过 \(\frac {\ 1\ }{2}\)。

稍加修改我们可以猜想：如果一个数组里有一元素超过 \(\frac {\ 1\ }{3}\)，那么同时删除 \(3\) 个不同的数，数量超过 \(\frac {\ 1\ }{3}\) 的数仍然超过 \(\frac {\ 1\ }{3}\)。

我们可以尝试证明它的正确性：

• 如果删除的 \(3\) 个不同的数都不是超过 \(\frac {\ 1\ }{3}\) 的元素，显然成立。

• 如果删除的 \(3\) 个不同的数有一个是超过 \(\frac {\ 1\ }{3}\) 的元素，设该元素有 \(m> \frac {\ 1\ }{3}\) 个，即需要证：

\[ \dfrac {m-1}{n-3}> \dfrac {n}{3}\Longrightarrow m> \dfrac {n(n-3)}{3}+1 \]

而：

\[ \dfrac {n(n-3)}{3}+1 \ge \dfrac {n}{3} \Longrightarrow (n-2)^2-1\ge 0\quad\{n\ge 3\} \]

故命题成立。

同样的证明方法可以推广到 \(k\)，得出：若一个数组里有一元素超过 \(\frac {\ 1\ }{k}\)，那么同时删除 \(k\) 个不同的数，数量超过 \(\frac {\ 1\ }{k}\) 的数仍然超过 \(\frac {\ 1\ }{k}\)。

不过很遗憾，如果 \(k\) 很大，只能用数组去存 \(cnt_i\)，但其内核仍然值得我们思考。