---
# System prepended metadata

title: '**Leetcode筆記(Top K Frequent Elements)**'
tags: [heap, 待解, medium, leetcode]

---

# **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://i.imgur.com/XIYEYIq.png)


**講解連結**
https://www.youtube.com/watch?v=YPTqKIgVk-k&ab_channel=NeetCode
Provided by. NeetCode

###### tags: `heap` `medium` `leetcode` `待解`