溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“Python如何返回前K個最頻繁的元素”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
題目描述
給出一個非空的整數數組，返回其中前k個出現最頻繁的元素。
Example
[1,1,1,2,2,3]，k = 2，輸出[1,2]
如果n是數組的大小，要求給出時間復雜度小于O(n log n)的算法。
算法分析
統計所有不同的數字出現的次數
找出出現次數前k大的數字
對于問題1，因為數字可能很大，我們需要借助HashMap進行統計，時間復雜度是O(n)的。對于問題2，有多種方法：一種簡單的方法是，對所有的次數快速排序，然后輸出前k個，這樣的時間復雜度是O(n log n)，不符合本題的要求。我們需要進行優化。
因為最后只需要返回k個數字，所以我們只需要一直維護一個大小為k的小根堆。當新的數字出現的次數大于堆中最小的次數時，我們對堆進行更新。時間復雜度是O(n log k)，是符合題目要求的。
那有沒有辦法進一步優化呢？因為k最壞情況下還是等于n的，n log k不是很理想。那么我們就需要換一種排序的方法。有一種排序的方法，其復雜度只和需要排序的數字的大小有關，而在本題中，需要排序的數字大小至多為n（某個數出現了n次）。答案是桶排序！桶排序就是用一個數組bucket記錄每個數字出現的次數，每次把數字丟到相應編號的桶中，然后從后往前窮舉每一個桶，取出其中的元素直到取滿k個。時間復雜度是O(n)。
最后本問題的最優算法的時間復雜度是O(n)。
參考程序
“Python如何返回前K個最頻繁的元素”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
