这道“简单”题，可以用哈希表解了，但题上要求时间复杂度O(n)，空间复杂度O(1)，我想不出来，就翻评论，它提到的是听都没听过的摩尔投票法。

找了个比较有趣的例子帮助我理解：

多国开战，各方军队每次派一个士兵来两两单挑，每次单挑士兵见面一定会和对方同归于尽，最后只要哪边还有人活着就算胜利，那么最后一定是没有人活着，或者活下来的都是同一势力。

那么活下来的势力一定就是参战中势力最雄厚的嘛(指人最多)？不是的，假设总共有2n+1个士兵参战，其中n个属于一方，另n个属于另一方，最后一方势力只有一个人，也许前两方杀红了眼两败俱伤了，最后被剩下的一个人捡漏了也是可能的。

那么辛苦杀敌到底是为了什么呢？只为了两件事

  1. 最后活下来的势力未必就是人最多的(也许会被人偷鸡)
  2. 人最多的势力如果不能活下来，只说明它的势力还不够强大，不足以保证赢得战争的胜利(指人数超过总参战人数的一半)
  3. 如果最后没有人活下来，说明此次参战的势力中，没有任何一只足够强大到一定会赢得胜利。

严谨的逻辑证明咱不会，凭理解写下思路，有错误的地方请大佬指正。

所以遍历一遍，每次清除一对不同势力的人，对最后活下来的势力单独验证一下究竟实力如何，对无人生还的情况，直接输出-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;

        for(auto num: nums) {
            if(!count) candidate = num;
            if(num == candidate) count++;
            else count--;
        }

        count = 0;
        for(auto num: nums) {
            if (num == candidate) count++;
        }
        
        return count * 2 > nums.size() ? candidate : -1;
    }
};

配合官方题解的ppt会好理解很多：Boyer-Moore 投票算法

它不配做一名“简单”同学~~