给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
思路
本题常见的三种解法：
-
哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)。
-
数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数 时间复杂度为 O(Ologn)。
-
摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 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;
}
};