Python前K個高頻元素怎么實現

本篇內容介紹了“Python前K個高頻元素怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

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

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

提示：

• 你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。

• 你的算法的時間復雜度必須優于 O(n log n) , n 是數組的大小。

• 題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的。

• 你可以按任意順序返回答案。

解題思路

思路：堆

首先審題，題目要求給定非空數組，求出頻率前 k 高的元素。提示中說明，算法時間復雜度要優于 O(nlogn)，又因為只需返回前 k 個頻率最高的元素，那么我們借助堆的思路，對于頻率 k 之后的不做處理，進而將時間復雜度優化到 O(nlogk)。

那么具體的做法如下：

• 先用哈希表統計元素出現的次數；

• 建立一個最小堆，維護最小堆：

• 當堆中元素數目小于 k，這里直接將元素插入；

• 若堆中元素數目等于 k 時，這個時候要將新元素出現頻率與堆頂元素出現頻率進行比較。若新元素出現頻率大于堆頂元素，那么彈出，插入新元素。

• 最終，堆中的 k 個即是要求的答案。

具體代碼實現如下（這里直接使用了 heapq 模塊）。

from typing import List

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

        # 哈希表統計元素出現頻率
        for num in nums:
            if num not in hash_map:
                hash_map[num] = 0
            hash_map[num] += 1
        
        # 建立最小堆，存儲頻率最大的 k 個元素
        import heapq

        pq = []

        for key in hash_map:
            if len(pq) < k:
                heapq.heappush(pq, (hash_map[key],key))
            elif hash_map[key] > pq[0][0]:
                heapq.heapreplace(pq, (hash_map[key],key))

        # 取出最小堆中的元素
        res = []
        while pq:
            res.append(pq.pop()[1])

        return res


# nums = [3,0,1,0]
# nums = [4,1,-1,2,-1,2,3]
# k = 2

# solution = Solution()

# print(solution.topKFrequent(nums, k))

“Python前K個高頻元素怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！