알고리즘/LeetCode

LeetCode 풀기 - 169. Majority Element

앤테바 2022. 2. 22. 06:13
반응형

169. Majority Element

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

 

Majority Element - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제)

솔루션1)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        half = len(nums)//2
        counter = Counter(nums)
        for n, count in counter.items():
            if count > half:
                return n

솔루션2)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]

솔루션3) Boyer-Moore 과반수 투표 알고리즘

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        major = 0
        for n in nums:
            if count == 0:
                major = n
                count += 1
            elif count == major:
                count += 1
            else:
                count -= 1
                
        return major
반응형