[Leetcode] 169. Majority Element

問題のショートカット

一般入力の場合:

hash map

Time Complexity: O(n)O(n)O(n)
Spcae Complexity: O(n)O(n)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)

2つの数値のみを入力します。

sort

Time Complexity: O(nlog⁡n)O(n\log n)O(nlogn)
Spcae Complexity: O(1)O(1)O(1) or O(n)O(n)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)O(n)O(n)
Spcae Complexity: O(1)O(1)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