Majority Element

•

문제 링크 : LeetCodeMajority Element - LeetCode

•

문제 설명 : nums 에서 가장 많이 존재하는 숫자(전체 요소 갯수 중 절반 이상)을 반환

•

풀이 방법

◦

dict를 사용하거나, count를 진행하며 문제를 풀었다.

◦

문제상에서는 두 방법 모두 시간차이는 크게 없었다.

•

시간복잡도 : O()O()O()

•

성공 코드(count 방식)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        target_num = nums[0]
        target_count = 1

        for i in range(1, len(nums)):
            if target_num != nums[i]:
                target_count -= 1
                if target_count == 0:
                    target_num = nums[i]
                    target_count = 1
            else:
                target_count += 1
        
        return target_num
Python
복사

•

성공 코드 (dict 방식)

from collections import defaultdict

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        info = defaultdict(int)
        keys = set()

        for num in nums:
            keys.add(num)
            info[num] += 1
        
        for key in keys:
            if info[key] > len(nums) // 2:
                return key
JavaScript
복사