题目
现在有人把一长串名字依次念出来，其中有些名字会被念很多次。
你的目标是：在听完整个序列后，手里留下一个名字，并且满足下面的条件：
- 已知一定存在某个名字，它出现次数超过总次数的一半；你最后留下的名字必定就是它。
限制是：你只能有一个计数器，并且脑中任意时刻只能记住一个名字。
你能做到吗？
分析
可以。做法如下：
先在脑中记一个“候选名字”\(C\)，再配一个计数器\(k\)。
- 一开始令\(k=0\)；
- 每听到一个名字\(x\)：
- 若\(k=0\)，就把\(C\)改成\(x\)，并令\(k=1\)；
- 若\(k>0\)且\(x=C\)，则令\(k\to k+1\)；
- 若\(k>0\)且\(x\ne C\)，则令\(k\to k-1\)。
全部名字念完后，输出当前记住的名字\(C\)即可。
为什么这样做一定对？关键在于“成对抵消”。
每当我们把一个当前候选名字和一个不同的名字配成一对并一起删去时，“是否存在多数名字”这个事实不会改变。因为如果某个名字\(M\)原来出现了超过一半的次数，那么删去一对不同名字后，至多删去一个\(M\)，同时总长度减少\(2\)，于是\(M\)在剩余序列中仍然超过一半。
更具体地说，若原序列长度为\(n\)，\(M\)出现了\(m\)次，且\(m>\frac{n}{2}\)。删去一对不同名字后：
- 如果这一对里没有\(M\)，那么\(M\)仍出现\(m\)次，而新长度是\(n-2\)，显然仍有\(m>\frac{n-2}{2}\)；
- 如果这一对里恰有一个\(M\)，那么\(M\)变成\(m-1\)次，而新长度仍是\(n-2\)。这时
\[ m-1>\frac{n}{2}-1=\frac{n-2}{2}.\]
所以，多数名字在这种“删去两个不同名字”的操作下不会改变。
于是我们可以想象：把整串名字中尽可能多的“不同名字对”都删掉。若原来存在多数名字\(M\)，那么删到最后不可能把它全部删光；而且最后剩下的名字如果还有多个种类，就还能继续删去一对不同名字，矛盾。所以最后若还有剩余，必然全是同一个名字，而这个名字只能是多数名字。
上面的计数方法，正是在用一个名字和一个计数器来模拟这个“不断配对删去不同名字”的过程：
- 计数器\(k\)表示当前还没有被抵消掉的候选名字个数；
- 遇到相同名字，就相当于又多了一个未抵消的候选名字；
- 遇到不同名字，就让它和一个候选名字同归于尽，因此\(k\)减\(1\)；
- 当\(k\)降到\(0\)时，说明当前这一批未抵消的候选名字已经全被配光了，后面可以重新开始记新的候选者。
因此，这个过程结束后留下的候选名字，正是“把所有不同名字尽量成对抵消之后可能剩下的那个名字”。如果多数名字存在，它一定就是这个候选名字。
所以答案是：能做到。上面这套规则就是所需方法。
补充说明：上面题目额外保证了“多数名字”确实存在，所以算法最后输出的候选名字就一定正确。更一般地说，即使不作这个保证，这套方法仍然可以在一遍扫描中找出一个候选名字；只是当根本不存在超过一半的名字时，它最后输出的候选者未必真是多数名字。这时若想严格判断“是否真的有多数名字”，还需要再做一次验证统计。