LeetCode 169. Majority Element

파이썬 알고리즘 인터뷰 83번(리트코트 169번) Majority Element
https://leetcode.com/problems/majority-element/

나의 풀이

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums) // 2]

다른 풀이1

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = collections.defaultdict(int)
        for num in nums:
            count[num] += 1
            if count[num] > len(nums) // 2:
                return num

다른 풀이2

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        if len(nums) == 1:
            return nums[0]
        half = len(nums) // 2
        a = self.majorityElement(nums[:half])
        b = self.majorityElement(nums[half:])
        return [a, b][nums.count(b) > half]

• 가끔 이 책에서 추천하는 풀이는 굳이? 싶을 때가 있다.
• 이 문제를 굳이 분할 정복 단원에서 다루며 이런 방법으로 풀 필요가 있을까 싶다.

다른 풀이3(Moore Voting Algorithm)

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