[분할정복] Leet code 169. Majority Element

리트코드 169번
과반수 이상을 차지하는 숫자 찾기

이 문제의 포인트는 O(N)의 시간복잡도와 O(1)의 공간복잡도로 푸는 것이다.
따라서 브루트 포스로는 구할 수 없습니다.

풀이1. Counter

• counter는 O(N)의 복잡도를 갖습니다. 하지만 most_common이 sort함수를 내부적으로 사용하기 때문에 nlogn을 갖게 됩니다!

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freqs = collections.Counter(nums)

        return freqs.most_common(1)[0][0]

풀이2. defaultDict

• 그래서 전체조회 한번과 그렇게 얻은 key들로 직접 과반수(n//2)를 넘는지 체크하면 O(n)으로 풀이가 가능합니다. 앞부분은 counter를 써도 되겠네요🧐

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freqs = collections.defaultdict(int)

        for num in nums:
            freqs[num] += 1

        for key in freqs:
            if freqs[key] > len(nums)//2:
                return key

풀이3. sort

• sorted함수를 쓰기때문에 O(nlogn)이지만 풀이가 간단하고 아이디어가 좋아서 가져와봤어요. 정렬을 했을 때 빈도가 과반수가 넘는다면 항상 len(nums)//2의 인덱스에는 위치할 것이기 때문입니다

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