【Leetcode 筆記】 347. Top K Frequent Elements

題目解釋

給定一個整數陣列 nums 和一個整數 k，傳回 k 個最常見的 elelments，可以按任意順序回傳答案。

範例

• 輸入: nums = [1, 1, 1, 2, 2, 3], k = 2
• 輸出: [1, 2]

最佳解法 (Follow-up)

先建立 hash map 後再使用 heap 來解決。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = collections.Counter(nums)

        return heapq.nlargest(k, iterable=counts.keys(), key=counts.get)

時間複雜度

O(nlogk)，n 是 nums 的元素個數，而 k 就是要 heap 要維持的元素數，在維持 heap 時只需要 O(nlogk) 的 time complexity 即可。

冷知識

python 的 heapq 底層用的是 min heap，若要存 max heap，可以考慮存進去時加負號，參考連結。

空間複雜度

O(n)，Counter 的 hash map 需要 O(n) 空間才能儲存。

正常解法

這個方法分別 traverse nums 一次建立 hash map 後再做 O(nlogn) 的 sort，所以時間複雜度跟空間複雜度都是 O(n)。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hash_map = dict()

        for n in nums:
            if n not in hash_map:
                hash_map[n] = 1
            else:
                hash_map[n] += 1

        sorted_hash_map = dict(sorted(hash_map.items(), key=lambda item: item[1], reverse=True))

        count = 0
        results = []
        for key, value in sorted_hash_map.items():
            results.append(key)
            count += 1
            if count == k:
                break

        return results

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26