1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 229. Majority Element II
"""
given an integer array of size 'n', find all elements that appear more than n
/ 3 times (floored)
"""
class Solution(object):
def majorityElement(self, nums):
if not nums:
return []
cnt1, cnt2, cdd1, cdd2 = 0, 0, 0, 1
for n in nums:
if n == cdd1:
cnt1 += 1
elif n == cdd2:
cnt2 += 1
elif cnt1 == 0:
cdd1, cnt1 = n, 1
elif cnt2 == 0:
cdd2, cnt2 = n, 1
else:
cnt1, cnt2 = cnt1 - 1, cnt2 - 1
return [n for n in (cdd1, cdd2) if nums.count(n) > len(nums) // 3]
if __name__ == "__main__":
obj = Solution()
print(obj.majorityElement([3, 2, 3])) # expect: 3
print(obj.majorityElement([1])) # expect: 1
print(obj.majorityElement([1, 2])) # expect: 1 2
|