229. Majority Element II.md

229. Majority Element II

Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Thinking:

• Method 1：Map

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++){
            map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1: 1);
        }
        int cmp = len / 3;
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        for(Map.Entry<Integer, Integer> entry : set){
            if(entry.getValue() > cmp)
                result.add(entry.getKey());
        }
        return result;
    }
}

• Method 2: Moore's voting algorithm

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        if(nums.length == 1){
            result.add(nums[0]);
            return result;
        }
        int major1 = 0, major2 = 0, count1 = 0, count2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == major1)
                count1++;
            else if(major2 == nums[i])
                count2++;
            else if(count1 == 0){
                major1 = nums[i];
                count1 = 1;
            }else if(count2 == 0){
                major2 = nums[i];
                count2 = 1;
            }else{
                count1 --;
                count2 --;
            }
        }
        count1 = 0;
        count2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == major1) count1++;
            if(nums[i] == major2) count2++;
        }
        int cmp = nums.length / 3;
        if(count1 > cmp) result.add(major1);
        if(count2 > cmp && major2 != major1) result.add(major2);
        return result;
    }
}

二刷

1. Use map to save the appearance of current number and it appears times.

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new LinkedList<>();
        if(nums == null || nums.length == 0) return result;
        Map<Integer, Integer> map = new HashMap<>();
        for(Integer num : nums){
            map.put(num, map.containsKey(num) ? map.get(num) + 1: 1);
        }
        int cmp = nums.length / 3;
        Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
        for(Map.Entry<Integer, Integer> entry : entrySet){
            if(entry.getValue() > cmp){
                result.add(entry.getKey());
            }
        }
        return result;
    }
}

2. This question is a improvement of question 169. Majority Element.

• we use two counts to record the appearance number of majority.
• if same, we increase the count and not same, we minus the count number.
• this method will only record the most two majority numbers but won't check if appears more than L / 3.

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new LinkedList<>();
        if(nums == null || nums.length == 0) return result;
        else if(nums.length == 1){
            result.add(nums[0]);
            return result;
        }
        int major1 = 0, major2 = 0, cnt1 = 0, cnt2 = 0;
        for(int num : nums){
            if(num == major1){
                cnt1 ++;
            }else if(num == major2){
                cnt2 ++;
            }else if(cnt1 == 0){
                major1 = num;
                cnt1 = 1;
            }else if(cnt2 == 0){
                major2 = num;
                cnt2 = 1;
            }else{
                cnt1 --;
                cnt2 --;
            }
        }
        cnt1 = 0; cnt2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == major1) cnt1++;
            else if(nums[i] == major2) cnt2++;
        }
        if(cnt1 > nums.length / 3)  result.add(major1);
        if(cnt2 > nums.length / 3)  result.add(major2);
        return result;
    }
}