宜宾网站建设公司

怎么使用heap和map

这篇文章主要讲解了“怎么使用heap和map”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么使用heap和map”吧！

宜昌网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。创新互联2013年开创至今到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

Top K 问题是面试中非常常考的算法题。

Leetcode 上这两题大同小异，这里以第一题为例。

怎么使用heap和map

题意：
给一组词，统计出现频率最高的 k 个。
比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。

有同学觉得这题特别简单，但其实这题只是母题，它可以升级到系统设计层面来问：

在某电商网站上，过去的一小时内卖出的最多的 k 种货物。

我们先看算法层面:

思路：

统计下所有词的频率，然后按频率排序取最高的前 k 个呗。

细节：

用 HashMap 存放单词的频率，用 minHeap/maxHeap 来取前 k 个。

实现：

  1. 建一个 HashMap ，遍历整个数组，相应的把这个单词的出现次数 + 1.

这一步时间复杂度是 O(n).

  1. 用 size = k 的 minHeap 来存放结果，定义好题目中规定的比较顺序
    a. 首先按照出现的频率排序；
    b. 频率相同时，按字母顺序。

  2. 遍历这个 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;
    }
}

感谢各位的阅读，以上就是“怎么使用heap和map”的内容了，经过本文的学习后，相信大家对怎么使用heap和map这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！


分享题目：怎么使用heap和map
文章URL：http://ybzwz.com/article/jeigih.html

其他资讯