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

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

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;
    }
};