""" 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()