leetcode 229. Majority Element II 摩尔投票法 Moore Voting + 要记住验证投票结果哦

深碍√TFBOYSˉ_ 2022-06-08 12:08 153阅读 0赞

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

题意很简单，就是寻找大于三分之一的元素，最简单的就是HashMap计数，这个很快。

建议和这道题[leetcode 169. Majority Element][] 一起学习，这道题采用的就是HashMap计数。

那就是**摩尔投票法 Moore Voting**，这种方法在之前那道题Majority Element 求众数中也使用了。题目中给了一条很重要的提示，让我们先考虑可能会有多少个众数，经过举了很多例子分析得出，任意一个数组出现次数大于n/3的众数最多有两个，具体的证明我就不会了，我也不是数学专业的。

那么有了这个信息，我们使用投票法的核心是找出两个候选众数进行投票，需要两遍遍历， 第一遍历找出两个候选众数，第二遍遍历重新投票验证这两个候选众数是否为众数即可，选候选众数方法和前面那篇Majority Element 求众数一样，由于之前那题题目中限定了一定会有众数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的众数可能不存在，所以要有验证。

摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 摩尔投票方法解决，记住吧
     * 
     * http://mabusyao.iteye.com/blog/2223195
     * 
     * 那就是摩尔投票法 Moore Voting，这种方法在之前那道题Majority Element 求众数中也使用了。
     * 题目中给了一条很重要的提示，让我们先考虑可能会有多少个众数，经过举了很多例子分析得出，
     * 任意一个数组出现次数大于n/3的众数最多有两个，具体的证明我就不会了，我也不是数学专业的。
     * 那么有了这个信息，我们使用投票法的核心是找出两个候选众数进行投票，需要两遍遍历，
     * 第一遍历找出两个候选众数，第二遍遍历重新投票验证这两个候选众数是否为众数即可，
     * 选候选众数方法和前面那篇Majority Element 求众数一样，由于之前那题题目中限定了一定会有众数存在，
     * 故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的众数可能不存在，所以要有验证。
     * 
     * 
     * 摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，
     * 将其从数组中删除。这样不断的删除直到无法再进行投票，
     * 
     * */
    public class Solution 
    {
        
        public List<Integer> majorityElement(int[] nums) 
        {
            List<Integer> res=new ArrayList<Integer>();
            if(nums==null || nums.length<=0)
                return res;
            else if(nums.length==1)
            {
                res.add(nums[0]);
                return res;
            }
    
            int m1=nums[0] , m2=0;
            int count1=1 , count2=0;    
            for(int i=1;i<nums.length;i++)
            {
                if(nums[i]==m1)
                    count1++;
                else if(nums[i]==m2)
                    count2++;
                else if(count1==0)
                {
                    m1=nums[i];
                    count1=1;
                }else if(count2==0)
                {
                    m2=nums[i];
                    count2=1;
                }else 
                {
                    count1--;
                    count2--;
                }
            }
    
            //验证检查过程
            count1=0;
            count2=0;
            for(int i=0;i<nums.length;i++)
            {
                if(nums[i]==m1)
                    count1++;
                else if(nums[i]==m2)
                    count2++;
            }
    
            if(count1>(nums.length/3))
                res.add(m1);
            if(count2>(nums.length/3))
                res.add(m2);    
            return res;
        }
    }

下面是C++的做法，做简单的做法就是使用map遍历，其实还有一个更加简单的做法，就是摩尔投票法，这个做法很棒，值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        vector<int> majorityElement(vector<int>& a)
        {
            vector<int> res;
            if (a.size() <= 0)
                return res;
    
            int m1 = INT_MIN, m2 = INT_MIN, count1 = 0, count2 = 0;
            for (int i : a)
            {
                if (i == m1)
                    count1++;
                else if (i == m2)
                    count2++;
                else if (count1==0)
                {
                    m1 = i;
                    count1 = 1;
                }
                else if (count2==0)
                {
                    m2 = i;
                    count2 = 1;
                }
                else
                {
                    count1--;
                    count2--;
                }
            }
    
            count1 = count2 = 0;
            for (int i : a)
            {
                if (i == m1)
                    count1++;
                else if (i == m2)
                    count2++;
            }
    
            if (count1 >= a.size() / 3)
                res.push_back(m1);
            if (count2 >= a.size() / 3)
                res.push_back(m2);
            return res;
        }
    };
    
    
    
        vector<int> majorityElementByMap(vector<int>& nums)
        {
            vector<int> res;
            map<int, int> mmp;
            for (int a : nums)
            {
                if (mmp.find(a) == mmp.end())
                    mmp[a] = 1;
                else
                    mmp[a] += 1;
            }
            map<int, int>::iterator i = mmp.begin();
            for (; i != mmp.end(); i++)
            {
                if (i->second > nums.size() / 3)
                    res.push_back(i->first);
            }
            return res;
        }
    };

[leetcode 169. Majority Element]: http://blog.csdn.net/jackzhang_123/article/details/78027272