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

二刷

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

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