九章演算法 | Yelp/Pocked Gem面試題：前K個最頻繁的元素

撰文 | JZ

專欄 | 九章演算法

題目描述

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

Example

[1,1,1,2,2,3]，k = 2，輸出[1,2]

如果n是數組的大小，要求給出時間複雜度小於O(n log n)的演算法。、

演算法分析

題目要求我們輸出前k個出現最頻繁的元素，因為k最大可以等於n，所以在最壞情況下我們需要統計所有數字的出現次數。那麼這個問題就分成了兩個部分：

1. 統計所有不同的數字出現的次數
2. 找出出現次數前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)。

參考程序

面試官角度分析

本問題考查hashmap的使用和對多種排序方法的理解。給出O(n log k)的演算法可以達到hire的程度，給出O(n)演算法可以達到strong hire。

LintCode相關題目練習

http://www.lintcode.com/en/problem/top-k-frequent-words/

http://www.lintcode.com/en/problem/top-k-frequent-words-map-reduce/

推薦閱讀：