首页 > 代码库 > 229. Majority Element II

229. Majority Element II

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.

用的是摩尔投票法,原版的算法是找一个数组出现次数大于数组长度半数的数(只有当数组中存在这样的数时,这个算法才会生效,而且不难理解,如果有也只可能有一个),方法就是定义一个变量m,记录当前的候选数字,再定义一个变量c,记录票数。然后遍历数组

1.当前数字如果和候选数字相等,c++;

2.当前数字和候选数字不相等

  1)若c == 0;那么令m = 当前数字;

  2)若从!= 0;那么c--;

如果这种数真的存在,那么这样遍历一遍,c绝对不为0。如果不能保证有这个数存在,那么这个算法不能用,得到的结果不能说明任何情况。

这道题是找出现次数大于长度的1/3的数,这样的数要是有的话最多两个,但是题目中没有说一定会有,所以最后要加上验证。设置两个变量m1,m2记录候选数,两个变量c1,c2记录出现的次数。

按照摩尔投票的方法,进行统计。然后再遍历一次数组,用来验证这两个数出现的次数是否大于n/3;情况有以下几种:

1.如果数组中存在这样的数,m1,m2中保存的一定是它(或者它们),且一定会通过验证。如果只存在一个,那么另外一个会在验证中被排除

2.如果数组中不存在这样的数,那么m1,m2 中的数不代表任何意义,也会在验证中排除。

这样就保证了不会错过一个好人,也不会放走一个坏人。

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums.length == 0)
        return res;
        int m1 = 0;
        int m2 = 0;
        int c1=0,c2 = 0;
        for(int i =0;i<nums.length;i++)
        {
            int x = nums[i];
            if(m1 == x)
            c1++;
            else if(m2 == x)
            c2++;
            else if(c1 == 0)
            {
                m1 = x;
                c1++;
            }
            else if(c2 == 0)
            {
                m2 = x;
                c2++;
            }
            else
            {
                c1--;
                c2--;
            }
        }
        c1 = 0;
        c2 = 0;
        for(int i = 0;i<nums.length;i++)
        {
            if(nums[i] == m1)
            c1++;
            else if(nums[i] == m2)
            c2++;
        }
        if(c1 > nums.length/3)
        res.add(m1);
        if(c2 > nums.length/3)
        res.add(m2);
        return res;
    }
}

 

229. Majority Element II