Solution using Moore’s Voting Algorithm
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
current = nums[0]
freq = 1
for i in range(1, len(nums)):
if current is None:
current = nums[i]
freq = 1
continue
if nums[i] == current:
freq += 1
else:
freq -= 1
if freq == 0:
current = None
return current
The idea assumes that a majority element do exist in the list. Each unique element cancels out each other and the last standing element is the answer.
