Categories
程式開發

面試常考算法題之Top K 問題


大家好,這裡是《齊姐聊算法》系列之Top K 問題。

Top K 問題是面試中非常常考的算法題。

面試常考算法題之Top K 問題 1

Leetcode 上這兩題大同小異,這里以第一題為例。

面試常考算法題之Top K 問題 2

題意:

給一組詞,統計出現頻率最高的k 個。

比如說“I love leetcode, I love coding” 中頻率最高的2 個就是I 和love 了。

有同學覺得這題特別簡單,但其實這題只是母題,它可以升級到系統設計層面來問:

在某電商網站上,過去的一小時內賣出的最多的k 種貨物。

我們先看算法層面:

思路:

統計下所有詞的頻率,然後按頻率排序取最高的前k 個唄。

細節:

用HashMap 存放單詞的頻率,用minHeap/maxHeap 來取前k 個。

實現:

建一個HashMap ,遍歷整個數組,相應的把這個單詞的出現次數+ 1.

這一步時間複雜度是O(n).

用size = k 的minHeap 來存放結果,定義好題目中規定的比較順序

a. 首先按照出現的頻率排序;

b. 頻率相同時,按字母順序。

遍歷這個map,如果

a. minHeap 裡面的單詞數還不到k 個的時候就加進去;

b. 或者遇到更高頻的單詞就把它替換掉。

時空複雜度分析:

第一步是O(n),第三步是nlog(k),所以加在一起時間複雜度是O(nlogk).

用了一個額外的heap 和map,空間複雜度是O(n).

代碼:

class Solution {
public List topKFrequent(String[] words, int k) {
// Step 1
Map map = new HashMap();
for (String word : words) {
Integer count = map.getOrDefault(word, 0);
count++;
map.put(word, count);
}

// Step 2
PriorityQueue minHeap = new PriorityQueue(k+1, new Comparator() {
@Override
public int compare(Map.Entry e1, Map.Entry e2) {
if(e1.getValue() == e2.getValue()) {
return e2.getKey().compareTo(e1.getKey());
}
return e1.getValue().compareTo(e2.getValue());
}
});

// Step 3
List res = new ArrayList();
for(Map.Entry entry : map.entrySet()) {
minHeap.offer(entry);
if(minHeap.size() > k) {
minHeap.poll();
}
}
while(!minHeap.isEmpty()) {
res.add(minHeap.poll().getKey());
}
Collections.reverse(res);
return res;
}
}

如果你喜歡這篇文章,記得給我點贊留言哦~你們的支持和認可,就是我創作的最大動力,我們下篇文章見!

我是小齊,紐約程序媛,終生學習者,每天晚上9 點,云自習室裡不見不散!

更多乾貨文章見我的Github: https://github.com/xiaoqi6666/NYCSDE