一、题意前提

给定 个投票编号，保证存在唯一一个编号，票数严格超过总票数一半。

设该编号得票数为 ，满足：

二、核心思想

不一样的数互相抵消，最后剩下的候选人，就是绝对多数。

三、维护变量

• ：当前候选代表
• ：候选存活计数器

四、算法规则

1. 若 ： 更换当前数为新候选，令 当前数，
2. 当前数与候选 相同： 自己人，
3. 当前数与候选 不同： 相互抵消，

遍历一遍所有数，最终 就是答案。

五、正确性通俗证明

设：

• 总人数：
• 绝对多数票数：
• 其余所有人总票数：

由条件：

变形得：

含义： 绝对多数的票数，比其他所有人票数加起来还要多。

其他全部票拿来跟它一对一抵消，也消不完； 最后一定剩下这个过半的数，算法必然正确。

六、时间空间复杂度

• 时间复杂度：只遍历一遍序列
• 空间复杂度：只用常数变量