Majority Element I & II

Major Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Such a problem definitely need a linear complexity algorithm. They call it Boyer-Moore Majority Vote Algorithm (The link provides the original paper, if you are interested).

It's a two step algorithm.
1. find the candidate of the majority element;

2. check if the candidate is the majority.

Figures are from GeeksforGeeks (always such irony).

Given an array: 1, 1, 4, 5, 1, 1, 5
Initialize the candidate = A[0], which is 1, count = 1
A[1] = 1, count = 2
A[2] = 4, count = 1
A[3] = 5, count = 0
candidate = 5, count = 1
A[4] = 1, count = 0
candidate = 1, count = 1
A[5] = 1, count = 2
A[6] = 5, count = 1
return candidate = 1

Check if 1 is the majority by count the number of appearance of 1. If count > n / 2, return true.

public class Majority {
    public int majorityElement(int[] num) {
        int candidate = findMajority(num);
        if (isMajority(num, candidate))
            return candidate;
        return -1;
        
    }
    private int findMajority (int[] num)
    {
        int candidate = num[0];
        int count = 1;
        for (int i = 1; i < num.length; i++)
        {
            if (num[i] == candidate)
                count++;
            else
                count--;
            if (count == 0)
            {
                candidate = num[i];
                count = 1;
            }
        }
        return candidate;
    }
    private boolean isMajority(int[] num, int candidate)
    {
        int count = 0;
        for (int i = 0; i < num.length; i++)
        {
            if (num[i] == candidate)
                count++;
        }
        return count > (num.length / 2);
    }
}

Actually, for this problem, only findMajority() method is needed, I just want to make it more accurate.

Major 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.


The idea is the same. Now we keep two candidates. Go through the array, and check if each one satisfies the condition.

    public List majorityElement(int[] nums) {
        List results = new ArrayList();
        if (nums == null || nums.length == 0)
            return results;
        int maj1 = nums[0], maj2 = nums[0];
        int count1 = 0, count2 = 0;
        for (int n : nums) {
            if (n == maj1)
                count1++;
            else if (n == maj2)
                count2++;
            else if (count1 == 0) {
                maj1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                maj2 = n;
                count2 = 1;
            } else {
                count1 --;
                count2--;
            }
        }
        if (maj1 == maj2 && count1 >= nums.length / 3) {
            results.add(maj1);
            return results;
        }
        count1 = 0; count2 = 0;
        for (int n : nums) {
            if (n == maj1)
                count1++;
            else if (n == maj2)
                count2++;
        }
        if (count1 > nums.length / 3)
            results.add(maj1);
        if (count2 > nums.length / 3)
            results.add(maj2);
        return results;
    }