Majority Element | LeetCode 824 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Majority Element | LeetCode 824

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/824/

 

주어진 배열에서 절반 이상을 차지하는 원소를 구하는 문제입니다.

단,  Could you solve the problem in linear time and in O(1) space?

 

 

💡 풀이

1. Majoirity Component는 다른 원소 다 합친거보다 더 많이 나온다는 점!

그냥 dictionary 이용해서 각 원소별 나온 횟수 count하는 걸로는 도저히 O(1) space만에 해결이 안 되어 discussion을 봤습니다.. ㅎ

 

핵심은 Majoirity Component는 다른 원소 다 합친거보다 더 많이 나온다는 점입니다.

Majoirty component가 나오면 +1, 다른게 나오면 -1을 하면 마지막에는 무조건 count가 양수여야 한다는 점이죠.

 

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

 

아래는 예시 input입니다. 

input	2	3	3
candidate	2	2	3
count	1	0	1

다른 candidate으로 시작했다가도 결국 3으로 세팅됨

 

input	3	2	3	4	3
candidate	3	3	3	3	3
count	1	0	1	0	1

중간에 다른 element가 끼어있더라도 결국 3이 됨

 

input	3	4	4	3	3
candidate	3	3	4	4	3
count	1	0	1	0	1

중간에 candidate이 바뀌었다가도 결국 3으로 돌아옴