[코테] 리트코드 분할 정복 169. Majority Element

169. Majority Element

문제 링크

https://leetcode.com/problems/majority-element/description/

문제 설명

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

제한 사항

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

입출력 예 #1

1. Input : nums = [3,2,3]
2. Output : 3

입출력 예 #2

1. Input : nums = [2,2,1,1,1,2,2]
2. Output : 2

문제 풀이

1. 브루트 포스로 과반수 비교
2. 다이나믹 프로그래밍
3. 분할 정복
4. 파이썬다운 방식

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

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

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 [b, a][nums.count(a) > half]

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