怎么使用heap和map

這篇文章主要講解了“怎么使用heap和map”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么使用heap和map”吧！

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

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

題意：
給一組詞，統計出現頻率最高的 k 個。
比如說 “I love leetcode, I love coding” 中頻率最高的 2 個就是 I 和 love 了。

有同學覺得這題特別簡單，但其實這題只是母題，它可以升級到<span >系統設計</span>層面來問：

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

我們先看算法層面:

<span >思路：

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

<span >細節：

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

<span >實現：

1. 建一個 HashMap <key = 單詞，value = 出現頻率>，遍歷整個數組，相應的把這個單詞的出現次數 + 1.

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

2. 用 size = k 的 minHeap 來存放結果，定義好題目中規定的比較順序
   a. 首先按照出現的頻率排序；
   b. 頻率相同時，按字母順序。

3. 遍歷這個 map，如果
   a. minHeap 里面的單詞數還不到 k 個的時候就加進去；
   b. 或者遇到更高頻的單詞就把它替換掉。

<span >時空復雜度分析：

第一步是 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;
    }
}

感謝各位的閱讀，以上就是“怎么使用heap和map”的內容了，經過本文的學習后，相信大家對怎么使用heap和map這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！