Majority Element II (LC-0229)

class Solution:
    def majorityElement(self, nums):
        
        def extendedBoyerMoore(nums, k):
            if k < 1: return []
            cache = {}
            for num in nums:
                if num in cache:
                    cache[num] += 1
                elif len(cache) < k:
                    cache[num] = 1
                else:
                    for key in list(cache.keys()):
                        if cache[key] == 1:
                            del cache[key]
                            continue
                        cache[key] -= 1
            
            count_map = {}
            for num in nums:
                if num in cache:
                    count_map[num] = count_map.get(num, 0) + 1

            result = []
            n = len(nums)
            for key, count in count_map.items():
                if count > (n // k):
                    result.append(key)
            
            return result
        
        return extendedBoyerMoore(nums, 3)