Count the occurrences of each element using a hash map. Then return the element whose count exceeds ⌊n / 2⌋. This is the most intuitive approach.
Maintain a candidate and a count. Iterate through the array: if count is 0, set the current element as the candidate. Increment count if the current element matches the candidate, otherwise decrement. The majority element is guaranteed to survive as the final candidate.
""" 0169.1 - Majority Element - Solution 1 - Hash Map Counting """
#####################################################################################
# Imports
#####################################################################################
from typing import List
from collections import Counter
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def majorityElement(self, nums: List[int]) -> int:
"""Majority Element Function"""
counts = Counter(nums)
return max(counts.keys(), key=counts.get)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().majorityElement([3, 2, 3])) # 3
print(Solution().majorityElement([2, 2, 1, 1, 1, 2, 2])) # 2
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0169.2 - Majority Element - Solution 2 - Boyer-Moore Voting Algorithm """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def majorityElement(self, nums: List[int]) -> int:
"""Majority Element Function"""
candidate = 0
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().majorityElement([3, 2, 3])) # 3
print(Solution().majorityElement([2, 2, 1, 1, 1, 2, 2])) # 2
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()