力扣169、多数元素

思路：摩尔投票法

• 对于这道题目
• 因为所求元素个数是大于 n / 2的；
• 那么所求元素的个数减去不同于所求元素的个数，最后所得的值的个数必然大于0，也就是最后赢家就是所求元素。
• 我们可以从第一个元素开始，如果它在这个过程中个数为0，那么他就不是所求元素，更新它

代码

int majorityElement(int* nums, int numsSize){
    int num = nums[0], cnt = 1;
    for (int i = 1; i < numsSize; i++) {
        if (num != nums[i]) {
            if (cnt == 0) num = nums[i], cnt = 1;
            else --cnt;
        } else cnt++;
    }
    return num;
}

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