[LeetCode][Python3] 169. Majority Element

Problem :

https://leetcode.com/problems/majority-element/description/

My Solution :

class Solution:

def majorityElement(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

counter = {}

for n in nums:

counter[n] = counter.setdefault(n, 0) + 1

for n, count in counter.items():

if count > len(nums) // 2:

return n

Comment :

위 풀이는 문제를 처음 접했을 때 별 고민없이 접근했던 방법이다.

아래 풀이는 내가 몰랐던 Boyer–Moore majority vote algorithm을 이용한 것이다.

My Solution2 :

class Solution:

def majorityElement(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

count = 0

major = None

for n in nums:

if count == 0:

major = n

if n == major:

count += 1

else:

count -= 1

return major