Boyer-Moore 알고리즘(=Majority Voting Algorithm)

본문에서 언급되는 알고리즘은 문자열 검색과는 다른 알고리즘입니다.

 

특정 배열이 있을 때, 그 배열에서 과반수를 차지하는 아이템이 어떤 것인지 찾는 알고리즘입니다.

 

Time Complexity: O(n)

Space Complexity: O(1)

 

과반수를 차지하는 아이템은 count > size(nums)/2 의 특성을 가지고 있습니다.

 

def majorityElement(nums: List[int]) -> int:
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)

    return candidate

 

 

 

 

https://www.youtube.com/watch?v=gY-I8uQrCkk