169. Majority Element (Array, Hash Table, Divide and Conquer, Sorting, Counting)

링크 - https://leetcode.com/problems/majority-element/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) Hash Map

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hash_map = defaultdict(int)
        max_freq = 0
        ans = 0

        for num in nums:
            hash_map[num] += 1
            if hash_map[num] > max_freq:
                max_freq = hash_map[num]
                ans = num

        return ans

Time Complexity: O(n)

Space Complexity: O(n)

2) Boyer-Moore Voting Algorithm

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1

        return candidate

Time Complexity: O(n)

Space Complexity: O(1)