LeetCode HOT100 - 多数元素

关键是进阶的 O(1) 空间复杂度的摩尔投票法（https://leetcode.cn/problems/majority-element/solutions/2362000/169-duo-shu-yuan-su-mo-er-tou-piao-qing-ledrh）

一个关键的出发点是类似于二分查找中位数时，将 大于等于 中位数的设置为 1，否则设置为 -1，这样因为中位数的定义，最后数组的和应该是大于 0 的

这里类似于使用这种元素个数的性质

记众数 x 的值为 1 ，其他元素统一设置成 -1，那么最后的和也是大于 0

接下来是看这个设置是否有进一步的结论

因为如果仅是这样设置我们或许仍要使用二分，这样时间复杂度并非 O(n)

结论
记数组的众数为 x ，我们假设的众数是 y 遍历并统计票数。当发生票数和 =0 时，剩余数组的众数一定不变，这是由于：

• 当 \(y = x\) ： 抵消的所有数字中，有一半是众数 x 。
• 当 \(y \neq x\) ：抵消的所有数字中，众数 x 的数量最少为 0 个，最多为一半。

利用此特性，每轮假设发生票数和 ``=0` 都可以缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = 0, cnt = 0;
        for (int i : nums) {
            if (!cnt) ans = i;
            cnt += i == ans ? 1 : -1;
        }
        return ans;
    }
};