169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

思路
本题常见的三种解法：

1. 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)。

2. 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数 时间复杂度为 O(Ologn)。

3. 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1)，为本题的最佳解法。

摩尔投票法：记数组首个元素为 n1，众数为 x ，遍历并统计票数。当发生 票数和 =0时，剩余数组的众数一定不变 ，这是由于：

• 当 n1=x： 抵消的所有数字中，有一半是众数 x。
• 当 n1≠x： 抵消的所有数字中，众数 x的数量最少为 0 个，最多为一半。

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

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        const int len = nums.size();
        int vote = 0;//票数
        int x;//众数
        for(auto num : nums){
            if(!vote)   x = num;
            if(num == x){
                vote++;
            }else{
                vote--;
            }
        }
        return x;
    }
};