229.-majority-element-ii.md

229. Majority Element II

• Medium
• Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Analysis

The first idea is that we create a dictionary recording how many times has the element appeared in the array, then when the count is over n/3, we record it and make sure we are not going to record it again.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        seen=collections.defaultdict(int)
        n=len(nums)
        ans=[]
        for i in nums:
            seen[i]+=1
            if seen[i]>n/3:
                ans.append(i)
                seen[i]=-n
        return ans

Then I read about the Boyer-Moore algorithom. The idea of this is that we can use difference votes to cancel out the majority. Say if we have 5 X and 4 Y. Then by cancelling out, there would be a X left. That means that X is the majority of this array.

Now since we are looking for things that appeared more than n/3 times, we would need 2 "majorities" to solve that.

def majorityElement(self, nums):
        if not nums:
            return []
        count1, count2, candidate1, candidate2 = 0, 0, 0, 1
        for n in nums:
            if n == candidate1:
                count1 += 1
            elif n == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1, count1 = n, 1
            elif count2 == 0:
                candidate2, count2 = n, 1
            else:
                count1, count2 = count1 - 1, count2 - 1
        return [n for n in (candidate1, candidate2)
                        if nums.count(n) > len(nums) // 3]