# **Leetcode筆記(Top K Frequent Elements)**
:::info
:information_source: 題目 : Top K Frequent Elements, 類型 : heap , 等級 : medium
日期 : 2023/04/20，2023/06/26，2023/12/04，2024/10/20，2025/03/31
:::
### 嘗試
時間複雜度：O(nlogn)。其中n是nums的長度，Counter內部使用了哈希表實現，計算出現次數的時間複雜度為O(n)，most_common方法會先對字典進行排序，時間複雜度為O(nlogn)
但它想要更小的時間複雜度
```python
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 會回傳dict
statis = Counter(nums)
# [('key1', value1), ('key2', value2)]
# 會按照value最大的排在最前面
temp = statis.most_common()
res = list()
for i in range(k):
res.append(temp[i][0])
return res
```
2023/06/26
用heap去解
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
record = {}
for c in nums:
record[c] = 1 + record.get(c, 0)
minHeap = [] # 長度為0
# key為字母 val為出現次數
for key, val in record.items():
if len(minHeap) < k: # ??為什麼不是 <= k個
heapq.heappush(minHeap, (val, key))
else:
heapq.heappushpop(minHeap, (val, key))
return [key for val, key in minHeap]
```
2023/12/04
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
hashmap = collections.defaultdict(int)
for n in nums:
hashmap[n] += 1
maxHeap = []
for key, value in hashmap.items():
maxHeap.append([-value, key])
heapq.heapify(maxHeap)
res = []
while k:
fre, n = heapq.heappop(maxHeap)
res.append(n)
k -= 1
return res
```
2024/10/20
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
record = collections.defaultdict(int)
for n in nums:
record[n] += 1
maxHeap = []
for key, val in record.items():
maxHeap.append([-val, key])
heapq.heapify(maxHeap)
res = []
while k:
val, key = heapq.heappop(maxHeap)
res.append(key)
k -= 1
return res
```
2025/03/31
今天是旅行回來之後回歸lc第一天
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
record = collections.defaultdict(int)
for n in nums:
record[n] += 1
maxHeap = []
for n, count in record.items():
maxHeap.append([-count, n])
heapify(maxHeap)
res = []
while k:
count, n = heappop(maxHeap)
res.append(n)
k -= 1
return res
```
---
### **優化**
时间复杂度：
第一个for循环将nums中的元素存储到count字典中，所以时间复杂度是O(N)
第二个for循环遍历了count字典，所以时间复杂度是O(N)
最后一个for循环遍历freq列表，所以时间复杂度是O(N)
因此，算法的总时间复杂度是O(N)
```python
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
# 最多次數 只可能是len(nums)次(即這個array的長度)
# 加1是為了把0次也算進去
freq = [[] for i in range(len(nums) + 1)]
# 先存進dict 統計freq
for num in nums:
count[num] = 1 + count.get(num, 0)
# 倒反儲存
for key, value in count.items():
freq[value].append(key)
# range(start, stop[, step])
res = []
for i in range(len(freq) - 1, 0, -1):
for freq_value in freq[i]: # 可能同數字的很多
if len(res) == k:
break
res.append(freq_value)
return res
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
from collections import Counter可以直接算list中東西的頻率，回傳成一個dict
Bucket sort
一個非比較排序。原理是建立一些桶子，每個桶子對應一資料區間，在將待排序資料分配到不同的桶中，桶子內部各自排序。由於並非比較排序，使用 Bucket sort 需要事先知道資料的範圍與分佈，才能決定桶子對應的區間。
dict.items()
回傳key, value
range(start, stop[, step])
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=YPTqKIgVk-k&ab_channel=NeetCode
Provided by. NeetCode
###### tags: `heap` `medium` `leetcode` `待解`
Sign in with Wallet
Connect another wallet