題目解釋
給定一個整數陣列 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
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