大家好，這里是《齊姐聊演算法》系列之 Top K 問題，
Top K 問題是面試中非常常考的演算法題，
Leetcode 上這兩題大同小異，這里以第一題為例，
題意：
給一組詞，統計出現頻率最高的 k 個，
比如說 “I love leetcode, I love coding” 中頻率最高的 2 個就是 I 和 love 了，
有同學覺得這題特別簡單，但其實這題只是母題，它可以升級到系統設計層面來問：
在某電商網站上，過去的一小時內賣出的最多的 k 種貨物，
我們先看演算法層面:
思路：
統計下所有詞的頻率，然后按頻率排序取最高的前 k 個唄，
細節：
用 HashMap 存放單詞的頻率，用 minHeap/maxHeap 來取前 k 個，
實作：
建一個 HashMap <key = 單詞，value = https://www.cnblogs.com/nycsde/p/出現頻率>，遍歷整個陣列，相應的把這個單詞的出現次數 + 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<String> topKFrequent(String[] words, int k) {
// Step 1
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
Integer count = map.getOrDefault(word, 0);
count++;
map.put(word, count);
}
// Step 2
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k+1, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
if(e1.getValue() == e2.getValue()) {
return e2.getKey().compareTo(e1.getKey());
}
return e1.getValue().compareTo(e2.getValue());
}
});
// Step 3
List<String> res = new ArrayList<>();
for(Map.Entry<String, Integer> 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/56155.html
標籤：其他