首页 > 代码库 > 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.

此题和major element的不同在于,由n/2 变成了n/3,那么看看再major element中用到的方法在这里还能不能继续用了:

1.hashmap,这个是可以的,代码如下:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

public class Solution {

    public List<Integer> majorityElement(int[] nums) {

        Map<Integer,Integer> map = new HashMap<>();

        List<Integer> res = new ArrayList<Integer>();

        for(int i=0;i<nums.length;i++){

            map.put(nums[i],map.getOrDefault(nums[i],0)+1);

        }

        for(int key:map.keySet()){

            System.out.println(key);

            System.out.println(map.get(key));

            if(map.get(key)>nums.length/3){

                res.add(key);

            }

        }

        return res;

    }

}

 

2.moor voting algorithm

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

public class Solution {

    public List<Integer> majorityElement(int[] nums) {

        List<Integer> res= new ArrayList<>();

        if(nums.length==0) return res;

        int major1 = nums[0];

        int major2 = nums[0];

        int count1 = 0;

        int count2 = 0;

        for(int i=0;i<nums.length;i++){

            if(major1==nums[i]){

                count1++;

            }else if(major2==nums[i]){

                count2++;

            }else if(count1==0){

                major1 = nums[i];

                count1++;

            }else if(count2==0){

                major2= nums[i];

                count2++;

            }else{

                count1--;

                count2--;

            }

        }

        count1=0;

        count2=0;

        for(int i=0;i<nums.length;i++){

            if(major1==nums[i]) count1++;

            else if(major2==nums[i]) count2++;

        }

        if(count1>nums.length/3) res.add(major1);

        if(count2>nums.length/3) res.add(major2);

        return res;

    }

}

229. Majority Element II