Python前K個高頻元素怎么實現(xiàn)

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

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

題目

給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例 1:

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

示例 2:

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

提示：

你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)。
你的算法的時間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小。
題目數(shù)據(jù)保證答案唯一，換句話說，數(shù)組中前 k 個高頻元素的集合是唯一的。
你可以按任意順序返回答案。

解題思路

思路：堆

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

那么具體的做法如下：

先用哈希表統(tǒng)計元素出現(xiàn)的次數(shù)；
建立一個最小堆，維護最小堆：

當堆中元素數(shù)目小于 k，這里直接將元素插入；
若堆中元素數(shù)目等于 k 時，這個時候要將新元素出現(xiàn)頻率與堆頂元素出現(xiàn)頻率進行比較。若新元素出現(xiàn)頻率大于堆頂元素，那么彈出，插入新元素。

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

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

from typing import List

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

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

網(wǎng)站標題：Python前K個高頻元素怎么實現(xiàn)
網(wǎng)頁鏈接：http://bm7419.com/article42/iidohc.html

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

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

猜你還喜歡下面的內(nèi)容