LeetCode #229 Majority Element II

Posted on | Post modified | In , , , , , , , ,

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.

Example 1:

1
2
Input: [3,2,3]
Output: [3]

Example 2:

1
2
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution

Method:

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        from collections import Counter
        dictionary = Counter(nums)
        ret = []
        majority = len(nums)//3
        
        for idx, key in enumerate(dictionary):
            if dictionary[key] > majority:
                ret.append(key)
        
        return ret