ps:problems:leetcode:347
Top K Frequent Elements
| ps | |
|---|---|
| 링크 | leetcode.com/… |
| 출처 | LeetCode |
| 문제 번호 | 347 |
| 문제명 | Top K Frequent Elements |
| 레벨 | Medium |
| 분류 |
기본 |
| 시간복잡도 | O(n+klogn) |
| 인풋사이즈 | n<=10^5 |
| 사용한 언어 | python 3.14 |
| 제출기록 | 22.91MB / 3ms |
| 최고기록 | 0ms |
| 해결날짜 | 2026/04/25 |
풀이
- 그냥 시키는대로 하면 되는 문제. 가장 간단한 구현 방법은, collection.Counter을 이용해서 frequency 들을 카운팅 한 뒤에, Counter의 most_common 함수를 사용하는 것이다. most_common 함수는 내부적으로 heapq.nlargest 함수를 이용한다. 시간복잡도는 O(n+klogn) 이다.
- 사실 실용적으로는 이 정도로 충분하다. 하지만 공식 솔루션 에서는 quick select 를 이용하는 O(n) 방법을, neetcode의 솔루션 에서는 min-heap을 이용하는 O(nlogk) 방법과 카운팅소트를 이용하는 O(n) 방법도 언급하고 있긴 하다.
코드
- problems/leetcode/q0347.py
"""Solution code for "LeetCode 347. Top K Frequent Elements". - Problem link: https://leetcode.com/problems/top-k-frequent-elements/ - Solution link: http://www.teferi.net/ps/problems/leetcode/347 """ import collections from typing import List class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: return [key for key, _val in collections.Counter(nums).most_common(k)]
ps/problems/leetcode/347.txt · 마지막으로 수정됨: 2026/04/25 16:31 저자 teferi
토론