LeetCode 169. Majority Element - Python

LeetCode 169. Majority Element - Python

 

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

 

Example 1:

Input: [3,2,3]
Output: 3

 

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

 

Solution 1:

#Boyer–Moore majority vote algorithm 사용
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

Solution 2:

#most_common : collections 모듈 - Counter 중 하나
#most_common은 입력된 값의 요소들 중 빈도수(frequency)가 높은 순으로 상위 n개를 리스트(list) 안의 투플(tuple) 형태로 반환한다. n을 입력하지 않은 경우, 요소 전체를 [('값', 개수)]의 형태로 반환한다.
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = collections.Counter(nums)
        return count.most_common(1)[0][0]

 

 

(참고 사이트)

[LeetCode][Python3] 169. Majority Element : https://www.snoopybox.co.kr/1896 - Boyer–Moore majority vote algorithm 사용

Majority Vote Algorithm : https://blog.myungwoo.kr/97

【LeetCode】169. Majority Element : https://blog.csdn.net/fuxuemingzhu/article/details/51288749 - most_common 사용

collections 모듈 - Counter : https://excelsior-cjh.tistory.com/94