剑指Offer 39. 数组中出现次数超过一半的数字

摘要：
摩尔投票法解决众数问题。

题目

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

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

示例1

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

限制：

• $1 <= 数组长度 <= 50000$

注意：本题与主站 169 题相同：LeetCode 169. 多数元素

---

摩尔投票法

摩尔投票法维护一个候选人对象major和一个计票对象cnt；
在遍历数组过程中定义三种状态：

重置状态：当计票对象cnt为0时，当前数字设为候选人major；
加权状态: 当major与当前数字相等时，cnt++;
对抗状态：当major与当前数字不同时，cnt--;

最终得到一个major和cnt，当确定原数组中存在超过一半的相同数（众数）时，major即为该众数；当不确定是否存在众数时，需要判断major是否为众数。

• C++

/*
 * 2021-6-26 18:55:47
 * author: etoa
 */
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int len = nums.size();
        int major = nums[0];        // 初始化候选人为数组第一个数
        int cnt = 1;                // 初始化计票变量，因为已经指派一个候选人，所以计票初始化为1
        for (int i = 1; i < len; i++) {
            if (!cnt) {             // 重置状态。如果计票为0，说明之前已经出现了对抗状态，到达了计票数0的下边界。需要重新指派候选人。
                major = nums[i];
                cnt = 1;
                continue;
            }   
            if (major == nums[i])   // 加权状态。
                cnt++;
            else                    // 对抗状态。
                cnt--;
        }
        return major;
    }
};

原题链接： 剑指Offer 39. 数组中出现次数超过一半的数字