【Leetcode】229. Majority Element II

Description

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.

Solution

public List<Integer> majorityElement(int[] nums) {
        //appear more than n / 3 times
        List<Integer> list = new ArrayList<>();
        int len = nums.length;
        //in O(1) space
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > len / 3) {
                list.add(entry.getKey());
            }
        }
        return list;
    }

Result

AC

Optimization

public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums.length == 0 || nums.equals(null)) {
            return list;
        }
        int nums1 = nums[0];
        int nums2 = nums[0];
        int count1 = 0;
        int count2 = 0;
        int len = nums.length;
        for (int i  = 0; i < len; i++) {
            if (nums[i] == nums1) {
                count1++;
            } else if (nums[i] == nums2) {
                count2++;
            } else if (count1 == 0) {
                nums1 = nums[i];
                count1 = 1;
            } else if (count2 == 0) {
                nums2 = nums[i];
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int n : nums) {
            if (n == nums1) {
                count1++;
            } else if (n == nums2) {
                count2++;
            }
        }
        if (count1 > len / 3) {
            list.add(nums1);
        }
        if (count2 > len /3) {
            list.add(nums2);
        }
        return list;
    }

Analyse

这个方法就是MajorityElement的方案的变形，但是要注意，一定开始是把count1和count2从0开始计算，若是都是开始从1开始计算，那么后面要计算count1和count2等于0的时候就会出问题。所以为了统一写法，就在majorityElement里直接改写法。

public int majorityElement(int[] nums) {
        int count = 0;
        int len = nums.length;
        int n = nums[0];
        for (int i = 0; i < len; i++) {
            if (nums[i] == n) {
                count++;
            } else if (count == 0) {
                n = nums[i];
                count = 1;
            } else {
                count--;
            }
        }
        return n;
    }