[Leetcode] 169. Majority Element (python)

#1.  문제

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

Majority Element - LeetCode

 

 

 

정수로 이루어진 길이 n의 nums 리스트에서 가장 많은 중복 요소를 리턴

 

# input
nums = [2,2,1,1,1,2,2]

# output
Output: 2

# explanation
요소 2가 4개로 가장 많기때문에 2를 리턴

 

---

#2.  풀이

 

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        nums_map = collections.defaultdict(int)

        for num in nums:
            nums_map[num] += 1

        return max(nums_map, key=nums_map.get)

 

여러가지 풀이 방법이 생각났는데 가장 처음으로 적용한 알고리즘이다.
중복 요소의 갯수를 세는 해시맵을 만들어서 가장 높은 값(중복 수)을 가진 요소를 리턴한다.
시간복잡도와 공간복잡도 모두 O(n)에 풀 수 있다.