摩尔投票

在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上

形象比喻

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

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

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

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

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

题目

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

• 示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

• 示例 2：

输入：[3,2]
输出：-1

• 示例 3：

输入：[2,2,1,1,1,2,2]
输出：2

解法

function majorityElement(nums: number[]): number {
    let alive = 0, count = 0
    for (const n of nums) {
        // 若当前无人生还，跟踪下一位士兵的势力
        if (!count) alive = n
        // 下一位士兵是自己人，那么幸存人数++
        if (alive === n) count++
        // 来了个敌人，同归于尽，幸存人数--
        else count--
    }

    count = 0
    for (const n of nums) {
        if (alive === n) count++
    }

    return count > nums.length / 2 ? alive : -1
};