关于java:必考算法之-Top-K-问题

大家好，这里是《齐姐聊算法》系列之 Top K 问题。

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

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

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

有同学感觉这题特地简略，但其实这题只是母题，它能够降级到零碎设计层面来问：

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

咱们先看算法层面:

思路：

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

细节：

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

实现：

建一个 HashMap <key = 单词，value = 呈现频率>，遍历整个数组，相应的把这个单词的呈现次数 + 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...