怎么使用heap和map

這篇文章主要講解了“怎么使用heap和map”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“怎么使用heap和map”吧！

Top K 問(wèn)題是面試中非常?？嫉乃惴}。

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

題意：
給一組詞，統(tǒng)計(jì)出現(xiàn)頻率最高的 k 個(gè)。
比如說(shuō) “I love leetcode, I love coding” 中頻率最高的 2 個(gè)就是 I 和 love 了。

有同學(xué)覺得這題特別簡(jiǎn)單，但其實(shí)這題只是母題，它可以升級(jí)到<span >系統(tǒng)設(shè)計(jì)</span>層面來(lái)問(wèn)：

在某電商網(wǎng)站上，過(guò)去的一小時(shí)內(nèi)賣出的最多的 k 種貨物。

我們先看算法層面:

<span >思路：

統(tǒng)計(jì)下所有詞的頻率，然后按頻率排序取最高的前 k 個(gè)唄。

<span >細(xì)節(jié)：

用 HashMap 存放單詞的頻率，用 minHeap/maxHeap 來(lái)取前 k 個(gè)。

<span >實(shí)現(xiàn)：

1. 建一個(gè) HashMap <key = 單詞，value = 出現(xiàn)頻率>，遍歷整個(gè)數(shù)組，相應(yīng)的把這個(gè)單詞的出現(xiàn)次數(shù) + 1.

這一步時(shí)間復(fù)雜度是 O(n).

2. 用 size = k 的 minHeap 來(lái)存放結(jié)果，定義好題目中規(guī)定的比較順序
   a. 首先按照出現(xiàn)的頻率排序；
   b. 頻率相同時(shí)，按字母順序。

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

<span >時(shí)空復(fù)雜度分析：

第一步是 O(n)，第三步是 nlog(k)，所以加在一起時(shí)間復(fù)雜度是 O(nlogk).

用了一個(gè)額外的 heap 和 map，空間復(fù)雜度是 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”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)怎么使用heap和map這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！