题解 | #数组中出现次数超过一半的数字#

// 摩尔投票法
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int maj = 0, cnt = 0;
        for(int& num : numbers) {
            if(num == maj) {
                cnt ++;
            } else if(--cnt < 0) {
                maj = num;
                cnt = 1;
            }
        }
        return maj;
    }
};

// 哈希法
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> m;
        int maj = 0, cnt = 0;
        for(int& num : numbers) {
            m[num]++;
            if(m[num] > cnt) {
                cnt = m[num];
                maj = num;
            }
        }
        return maj;
    }
};