LC 0169 [E] Majority Element - ALawliet/algorithms GitHub Wiki
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# O(n), O(n)
num_to_freq = Counter(nums)
for num, freq in num_to_freq.items():
if freq > n/2:
return num
def majorityElement(self, nums):
# O(n), O(1)
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate