Q.
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example:
Input: nums = [3,2,3]
Output: [3]
Input: nums = [1]
Output: [1]
Input: nums = [1,2]
Output: [1,2]
S1.
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
N = 3
candi = {}
for x in nums:
candi[x] = candi.get(x, 0) + 1
if len(candi) <= N-1:
continue
newCandi = {}
for key in candi:
val = candi[key]
if val > 1:
newCandi[key] = val - 1
candi = newCandi
res = []
for key in candi:
if nums.count(key) > len(nums)//N:
res.append(key)
return res
#O(n), O(1)
S2.
