Leetcode #229. Majority Element II

[yokostan]

Runtime only beats 5%, O(n) time & space:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) return res;

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

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && map.get(nums[i]) == -1) continue;
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            }
            if (map.get(nums[i]) > nums.length / 3) {
                map.put(nums[i], -1);
                res.add(nums[i]);
            }
            map.put(nums[i], map.get(nums[i]) + 1);
        }
        return res;
    }
}

The requirement is O(1):

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) return res;
        int num1 = nums[0], num2 = nums[0], count1 = 0, count2 = 0, len = nums.length;

        for (int i = 0; i < len; i++) {
            if (nums[i] == num1) count1++;
            else if (nums[i] == num2) count2++;
            else if (count1 == 0) {
                num1 = nums[i];
                count1 = 1;
            }
            else if (count2 == 0) {
                num2 = nums[i];
                count2 = 1;
            }
            else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == num1) count1++;
            else if (nums[i] == num2) count2++;
        }
        if (count1 > len / 3) res.add(num1);
        if (count2 > len / 3) res.add(num2);
        return res;
    }
}

And this is Boyce-Moore algorithm. https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html