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

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

成都創(chuàng)新互聯公司-專業(yè)網站定制、快速模板網站建設、高性價比金壇網站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式金壇網站制作公司更省心,省錢,快速模板網站建設找我們，業(yè)務覆蓋金壇地區(qū)。費用合理售后完善，10多年實體公司更值得信賴。

題目

---

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

示例 1:

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

示例 2:

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

提示：

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

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

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

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

解題思路

---

思路：堆

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

那么具體的做法如下：

• 先用哈希表統(tǒng)計元素出現的次數；

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

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

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

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

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

from typing import List

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

        # 哈希表統(tǒng)計元素出現頻率
        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個高頻元素怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注創(chuàng)新互聯網站，小編將為大家輸出更多高質量的實用文章！

網站標題：Python前K個高頻元素怎么實現
網頁鏈接：http://muchs.cn/article42/iidohc.html

成都網站建設公司_創(chuàng)新互聯，為您提供云服務器、虛擬主機、網頁設計公司、Google、網站改版、網站設計公司

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯