229. Majority Element II

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.

Solution

public class Solution {
     public List<Integer> majorityElement(int[] nums) {
        int a = 0;
        int b = 0;
        int m = 0;
        int n = 0;

        int size = nums.length;
        if (size <= 0) {
            return new ArrayList<>();
        }

        for (int i = 0; i < nums.length; i++) {
            if (a == nums[i]) {
                m++;
            } else if (b == nums[i]) {
                n++;
            } else if (m == 0) {
                a = nums[i];
                m = 1;
            } else if (n == 0) {
                b = nums[i];
                n = 1;
            } else {
                m--;
                n--;
            }
        }

        List<Integer> result = new ArrayList<>();
        if (m != 0 && verify(nums, a, size)) {


            result.add(a);
        }
        if (n != 0 && verify(nums, b, size) && b != a) {
            result.add(b);
        }

        return result;
    }

    private boolean verify(int[] nums, int candidate, int size) {
        int count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        return (double) count > (double) size / 3;
    }
}