0%
Loading ...

【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
數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.