Description
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
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
Follow up: Could you solve the problem in linear time and in O(1) space?
Solution
Python3
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
N = len(nums)
maj1, maj2, count1, count2 = None, None, 0, 0
for x in nums:
if x == maj1:
count1 += 1
elif x == maj2:
count2 += 1
elif count1 == 0:
maj1, count1 = x, 1
elif count2 == 0:
maj2, count2 = x, 1
else:
count1 -= 1
count2 -= 1
return [maj for maj in (maj1, maj2) if nums.count(maj) > N // 3]