[LeetCode]229. Majority Element II

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

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

Example 1:

Input: nums = [3,2,3] Output: [3]

Example 2:

Input: nums = [1] Output: [1]

Example 3:

Input: nums = [1,2] Output: [1,2]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

import math
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        stack = []
        A  = dict(zip(nums, [nums.count(i) for i in nums]))
        
        AReverse = dict(zip(A.values(),A.keys()))
        length = len(nums)
        limit = math.ceil(len(nums)/3)

        for i in AReverse:
      
            if i > limit:
                stack.append(AReverse[i])
            if len(nums) == 1:
                stack.append(AReverse[i])
        print(AReverse)
        return stack


# 아래의 예외케이스에서 막혔다. 
# 위와 같은 방식으로 key, value 의 위치를 바꾸면, 중복 value 가 key 에서 더하기 연산된다. 

# Input = [1,2]
# Output = []
# Expected = [1,2]

#Credit to @StefanPochmann for the following code:

def majorityElement(self, nums):
    ctr = collections.Counter()
    for n in nums:
        ctr[n] += 1
        if len(ctr) == 3:
            ctr -= collections.Counter(set(ctr))
    return [n for n in ctr if nums.count(n) > len(nums)/3]