Leetcode :: Majority element

Problem

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.

Guess

• 브루트포스, 단순 max count 등등.. 방법이야 많지만
• 내 목적은 아래와 같다.
  time - O(n)
  space - O(1)
  
• boyer-moore voting algorithm을 사용해 구현할 수 있다.

Solution

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if candidate == num else -1
                    
        return candidate