题意: 已知一个长度为n的序列中存在一个出现频率严格超过1/2的数, 求出它. (n≤5*10^5, 空间限制1MB, 数列中每个数≤maxlongint) 有一个奇妙的算法用于解决这个问题: 摩尔投票法.
以下称在序列中出现频率严格大于一半的数为majority.
性质: 如果序列中存在一个majority x, 那么, 删去两个不同的数, x仍是majority.
把序列分成两部分: x, 非x. 如果删去的两个数同属于非x, 显然成立; 如果一个属于x, 一个属于非x, 两部分的规模同时减小1. 根据数学归纳法, 性质得证.
基于这个性质, 我们可以设计一个算法: 如果序列中存在majority, 每次删去两个不同数, 最后一定会剩下一种数, 它就是majority. 如果不知道存不存在, 就再扫一遍验证.
仅将数据读一遍就能找出它. 设现在读入的数为x. 维护一个栈. 如果栈为空, 将x入栈. 否则, 比较x与栈顶元素: 相等, 则x入栈; 不等, 则弹栈, 同时删去两者. 循环不变式: 栈为空, 则前i项可全部抵消; 栈非空, 则栈中元素为前i项进行抵消操作后剩下的那一种数.
不需要一一记录栈中的每个元素, 因为它们相等. 只用记录它们是哪一种, 一共有多少个.
推广: 寻找在序列中出现频率严格大于1/3的数.
类比: 如果存在, 删去三个不同数, 原来出现频率超过1/3的数在新的序列里仍然超过1/3.
这样的数不可能多于两个. 先假设就存在两个: x和y. 把序列分成三部分: x, y, 非x且非y. 删去的三个数同属于非x且非y, 显然成立; 否则, 它们分别属于三个部分. 频率超过1/3等价于出现次数大于其他数之和的的一半. x的出现次数减1, 其他数出现次数之和减2, y同理. 也可以列个不等式. 如果只存在一个, 就令y为其他任意一种数(如果这样的y不存在, 命题显然成立). 上面的论证对x仍是成立的.
也许会疑惑这个算法与"摩尔"和"投票"有什么关系. "摩尔"不是物质的量的单位也不是一种鼹鼠, 而是一个老爷爷. 算法的正确性证明有另一种很妙的方式: 设m为序列中任意数, 令c=栈中元素数目*(栈中元素为m ? 1 : -1), 那么, 每读入一个m, c增加1(如果栈中元素为m或者没有元素, c为非负数, 绝对值+1; 如果栈中元素不是m, c为负数, 绝对值-1), 每读入一个非m, c增加或减少1(栈中元素为m, c为正数, 绝对值-1; 栈为空, c=0, 变为c=-1; 栈中元素非m, c为负数, 如果新数与它相同, 绝对值+1, 否则绝对值-1). 这就像投票. 同一派总是向你投正票, 其他人可能向你投正票, 也可能投负票. 如果你的派别占有绝对优势, 你一定会当选. 现在令m为majority, 则最终c为正数. 这当且仅当最终栈中元素为m.
杜教WC讲课时提到了这个经典算法, 将扩展为并行. 然后掉线了一会儿. QAQ
- 摩尔投票算法 (Boyer-Moore majority vote algorithm) - ywcpig的专栏 - 博客频道 - CSDN.NET
- Boyer-Moore majority vote algorithm - Wikipedia
- A Linear Time Majority Vote Algorithm 摩尔自己的网页, 有算法的演示. 看了一下他的主页, 网有点慢, 一张照片从上到下徐徐加载......一个带着墨镜和帽子, 背着双肩包, 头发雪白的老爷爷在蓝天白云的野外对你露出灿烂的微笑. :)
#include <cstdio>
using namespace std;
typedef long long ll;
int main()
{
int n, c = 0;
ll x, y;
scanf("%d", &n);
while (n--) {
scanf("%lld", &y);
if (c)
c += x == y ? 1 : -1;
else {
c = 1;
x = y;
}
}
printf("%lld\n", x);
return 0;
}