Majority Element II

Problem: Majority Element II

If we are asked to solve this problem in linear time and O(1) space, we need to use an algorithm called Boyer-Moore majority voting algorithm. The general idea of voting algorithm is that if an element is majority, it must once appear twice in continuous 3 elements. So we simply use a counter to check whether a number can appear like this. If there's such a number, we check the array again to see if it's proportion is really majority.

The difference between Boyer-Moore majority voting algorithm and solution to this problem, is that the algorithm considers n/2 as majority, while this problem considers n/3. The problem asks for more than floor(n/3), which actually means equal or more than n/3 + 1. Thus there can only be 2 majority numbers due to this requirement. We can use two temp numbers and two counters to solve this problem.

Code in Python:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        a = b = None
        ca = cb = 0
        for num in nums:
            if a == num:
                ca += 1
            elif b == num:
                cb += 1
            elif ca == 0:
                a, ca = num, 1
            elif cb == 0:
                b, cb = num, 1
            else:
                ca -= 1
                cb -= 1

        res = []
        ca_ = cb_ = 0
        for num in nums:
            if a == num:
                ca_ += 1
            if b == num:
                cb_ += 1
        if ca_ > len(nums) / 3:
            res.append(a)
        if cb_ > len(nums) / 3:
            res.append(b)

        return res

For details, pay attention to the sequence of if statement. We need to check both temp numbers first, or we will cause duplicate candidates or lose potential majority numbers.