LeetCode 229. Majority Element II

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

Note: The algorithm should run in linear time and in O(1) space.
'''

class Solution(object):
    #24ms, 11.6MB
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ht = {}
        for i in nums:
            if i in ht:
                ht[i] += 1
            else:
                ht[i] = 1
        return [i for i in ht if ht[i] > len(nums)//3]