Problem link
https://leetcode.com/problems/majority-element
Problem Summary
배열에서 n / 2번 이상 나온 원소를 찾는 문제. (과반수 이상 나온 원소)
Solution
시간 O(n), 공간 O(n)이상의 솔루션은 매우 쉽다 (sorting, hashmap, 등등)
하지만 follow up 문제인 시간 O(n), 공간 O(1)은 꽤 어려운데... 이거는 Boyer-Moore Voting Algorithm을 써야 한다.
Boyer-Moore Voting Algorithm 설명
위대한 ChatGPT의 도움으로 이해가 쉽게 설명하자면 쌍을 짝지어 없애는 방식이다.
간단히 말해 과반수 이상 나온 원소를 x라 하고 나머지들은 a라 하면 x는 과반수 이상 나오기 때문에 x가 나올 때마다 1씩 더하면 a가 나올 때마다 1씩 빼줘도 결국에는 항상 1 이상이 남게 된다.
예시인 [2,2,1,1,1,2,2]를 보면 앞의 2,2,1,1이 합쳐서 없어지고 후보가 1이 되지만 뒤에 2가 나오면서 다시 사라지고 마지막 2 한개만 남게 된다.
Source Code
시간: O(n), 공간: O(n) 솔루션
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt = defaultdict(int)
for n in nums:
cnt[n] += 1
for n in nums:
if cnt[n] > len(nums) // 2:
return n
return 0시간: O(n), 공간: O(1) 솔루션 (Boyer-Moore Voting Algorithm)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt = 0
ans = 0
for n in nums:
if cnt == 0:
ans = n
if ans == n:
cnt += 1
else:
cnt -= 1
return ans