[LeetCode] 347. Top K Frequent Elements

문제 링크 

https://leetcode.com/problems/top-k-frequent-elements/description/

Intuition

• 주어진 array에서 가장 중복이 많은 k개의 element를 결과값으로 반환 
• 그렇다면 정렬하고, 중복을 찾기 위해선 hash를 써야겠군 

Approach

• hash를 쓰기 위해서는 python의 dictionary를 사용 
• 가장 많이 중복되는 element 별로 저장된 dictionary를 그 후에 정렬!
• 정렬된 중복_숫자_맵 에서 k개의 key값을 반환 
• dict에서 get()함수는 parameter가 2개! 두번째 param은 optional로 조회하는 key 값이 없는 경우에 반환할 값을 설정 
  • numMap[num] = numMap.get(num,0) → numMap에서 num값의 키값이 없는 경우 0을 리턴 
  • dict[key] 로 조회했을 때 key가 없다면 에러 발생 
  • dict.get(key)로 조회했을 때 key가 없다면 None 리턴 

Complexity

여기 complexity는 좀 고민을 해보자..

Code

first submission: 

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

        numMap = dict()
        for num in nums: 
            numMap[num] = nums.count(num)
        
        ret = dict(sorted(numMap.items(), key=lambda x: x[1], reverse=True))
        return list(ret)[0:k]

time limit exeeded :( 두둥 

역시 count() 함수는 아니었나봐,, 더 쉬운 방법으로! 

 

2nd submission:

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

        numMap = dict()
        for num in nums: 
            numMap[num] = numMap.get(num,0) + 1
        
        ret = dict(sorted(numMap.items(), key=lambda x: x[1], reverse=True))
        return list(ret)[0:k]