找出一组数组中，出现次数超过数组长度一半的那个数，时间复杂度$\mathcal{O}(n)$，空间复杂度$\mathcal{O}(1)$，这种算法存在，叫摩尔投票 ( Moore voting )。
算法核心思想：所有选票中，不同的选票两两抵消，最后剩下的那张选票，就是选出的得票最多的那个人。
使用极限思维快速理解：有很多种选票，既然有一个人的票数过半，假设其余选票有下列两种情形：
-
它们可以各不相同，那么这些各不相同的选票“内部”也会互相抵消一部分，剩下的票数去对抗他们共同的敌人 —— 得票过半者，显然不能胜利；
-
它们也可以都选了另一个人，无论选票以什么顺序出现，相同的选票相加，不同的选票抵消，剩下的依旧是胜出者的选票。
下面借助LeetCode 169 Majority Element来讲解。
static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = nums[0], count = 1;
for (int i = 1, stop = nums.size(); i < stop; ++i) {
if (nums[i] == res) {
++count;
} else {
--count;
if (count == 0) {
res = nums[i];
count = 1;
}
}
}
return res;
}
};
代码理解：
胜出者res初始化为第一个人，当前胜出票数count初始化为 1，继续扫描数组，如果接下来选票选出的人与我们认为的胜出者相同，则胜出选票+1；如果不同，就将胜出者的票数-1，如果胜出的票数为0，那么就认为当前的人是胜出者，其胜出票数为 1。持续上述过程，直到扫描完毕整个数组，则最终的胜出者已经找到。