229 Majority Element II.py

# -*- coding: utf-8 -*0
"""
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.
Author: Rajeev Ranjan

"""

from collections import defaultdict


class Solution:
    def majorityElement(self, nums):
        """
        Since majority elements appears more than ⌊ n/3 ⌋ times, there are at most 2 majority number
        :type nums: list[int]
        :rtype: list[int]
        """
        cnt = defaultdict(int)
        for num in nums:
            if num in cnt:
                cnt[num] += 1
            else:
                if len(cnt) < 3-1:
                    cnt[num] += 1
                else:
                    for k in cnt.keys():
                        cnt[k] -= 1
                        if cnt[k] == 0:
                            del cnt[k]

        ret = []
        for k in cnt.keys():
            if len(filter(lambda x: x == k, nums)) > len(nums)/2:
                ret.append(k)

        return ret