Algorithm/LeetCode
[LeetCode]229. Majority Element II
Eric_Park
2021. 9. 29. 10:58
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]