[Leetcode] 169. Majority Element

문제 바로가기

일반적인 입력의 경우

hash map

Time Complexity: $O(n)$
Spcae Complexity: $O(n)$

# dict 사용
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = dict()
        half = len(nums) // 2
        
        for num in nums:
            if num not in count:
                count[num] = 0
            count[num] += 1
            if count[num] > half:
                return num

# dict의 sub class인 Counter 사용
import collections

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counter = collections.Counter(nums)
        return max(counter.keys(), key=counter.get)

단 두가지 숫자만 입력으로 들어오는 경우

sort

Time Complexity: $O(n\log n)$
Spcae Complexity: $O(1)$ or $O(n)$ <- if In-Place not allowed

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

Boyer-Moore Voting Algorithm

Time Complexity: $O(n)$
Spcae Complexity: $O(1)$

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        
        return candidate