数组中出现次数超过一半的数字

原题

相互抵消后，重新选择一个数

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0, val = -1;
        for (auto x : nums) {
            if (cnt == 0) {
                val = x, cnt = 1;
            } else {
                if (x == val) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        return val;
    }
};

摩尔投票法

https://www.freesion.com/article/58021369255/