39_MoreThanHalfNumber 数组中超过一半的元素

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

1.利用hashmap统计数组中元素出现的次数，如果次数大于数组长度的一半则返回该元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> nmap;
        int res;
        for(auto x: nums) {
            ++nmap[x];
            if (nmap[x] > nums.size()/2) {
                res = x;
            }
        }
    return res;
    }
};

2.排序后中间元素是该元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

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

假设遇到元素是众数，则票数加1，若非众数则减1。如果投票的和为0，则众数在后面的元素中。并且假设首先遇到的第一个元素是众数，如果出现投票总和为0，则重现开始新一轮的假设（众数）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0, count = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        // 验证 x 是否为众数，若假设一定存在则这部分不必要
        for(int num : nums)
            if(num == x) count++;
        return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
    }
};