Top K Frequent Elements

박수빈·2022년 2월 7일
0

leetcode

목록 보기
16/51

문제

  • 정수 리스트 nums
  • 정수 k
  • 자주 나오는 순으로 k개 return
  • 답이 unique 함이 보장됨

풀이

  • defaultdict 이용해서 list 돌면서 +=1 해주기
  • heap에 -freq를 우선순위로 넣어주기(클수록 우선순위 빠르도록)
  • k번 pop 해서 리턴
from collections import defaultdict
from heapq import heappush, heappop


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # counting frequency
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1
        
        # sort by frequency
        sortedList = []
        for key in freq:
            heappush(sortedList, [-freq[key], key]) # [priority, num]
        
        # finding k freq num.
        ans = []
        while k > 0 and sortedList:
            ans.append(heappop(sortedList)[1])
            k -= 1
        return ans      
  • heap 문제라서 이렇게 풀려고는 하는데, 그냥 lambda식 써서 하면 되지 않나?
from collections import defaultdict

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # counting frequency
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1
        
        # sort by frequency
        li = [[num, freq[num]] for num in freq]
        li.sort(key=lambda x: x[1], reverse=True)
        ans = [el[0] for el in li]
        
        return ans[:k]

결과

그냥 정렬을 이용한 두번째 풀이가 조금 더 빠르다...

profile
개발자가 되고 싶은 학부생의 꼼지락 기록

0개의 댓글