Top K Frequent Elements
문제
- 정수 리스트
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]
결과
nums
k
- 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]
결과
그냥 정렬을 이용한 두번째 풀이가 조금 더 빠르다...
Author And Source
이 문제에 관하여(Top K Frequent Elements), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Top-K-Frequent-Elements저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)