【LeetCode每日一题】229. 求众数 II【中等】哈希、数学

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3] 输出：[3] 示例 2：

输入：nums = [1] 输出：[1] 示例 3：

输入：[1,1,1,3,3,2,2,2] 输出：[1,2]  

提示：

1 <= nums.length <= 5 * 104 -109 <= nums[i] <= 109

题解： 最容易想到的当然就是哈希表了，算出符合条件的元素个数，用哈希表计数，再扫描一遍加入答案数组，但是竟然还有一种将空间复杂度优化到O(1)级别的方案，真是太不可思议了，叫摩尔投票法。

//哈希表实现
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        map<int, int> m;
        //对各元素计数
        for(auto e: nums){
            m[e]++;
        }
        //计算出n/3
        int cnt = nums.size() / 3 + 1;
        map<int, int>::iterator iter;
        vector<int> ans;
        //将符合条件的数加入答案数组
        for(iter = m.begin(); iter != m.end(); iter++){
            if(iter -> second >= cnt){
                ans.push_back(iter -> first);
            }
        }
        return ans;
    }
};

题解二：摩尔投票法

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;

        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
                vote1++;
            } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
                vote2++;
            } else if (vote1 == 0) { // 选择第一个元素
                element1 = num;
                vote1++;
            } else if (vote2 == 0) { // 选择第二个元素
                element2 = num;
                vote2++;
            } else { //如果三个元素均不相同，则相互抵消1次
                vote1--;
                vote2--;
            }
        }

        int cnt1 = 0;
        int cnt2 = 0;
        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        if (vote1 > 0 && cnt1 > nums.size() / 3) {
            ans.push_back(element1);
        }
        if (vote2 > 0 && cnt2 > nums.size() / 3) {
            ans.push_back(element2);
        }

        return ans;
    }
};