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

41次阅读

共计 1689 个字符,预计需要花费 5 分钟才能阅读完成。

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

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

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

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

有同学感觉这题特地简略,但其实这题只是母题,它能够降级到 <span style=”color:blue;font-weight:bold;”> 零碎设计 </span> 层面来问:

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

咱们先看算法层面:

<span style=”color:orangered;font-weight:bold;”> 思路:

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

<span style=”color:orangered;font-weight:bold;”> 细节:

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

<span style=”color:orangered;font-weight:bold;”> 实现:

  1. 建一个 HashMap <key = 单词,value = 呈现频率 >,遍历整个数组,相应的把这个单词的呈现次数 + 1.

    这一步工夫复杂度是 O(n).

  2. 用 size = k 的 minHeap 来寄存后果,定义好题目中规定的比拟程序
    a. 首先依照呈现的频率排序;
    b. 频率雷同时,按字母程序。
  3. 遍历这个 map,如果
    a. minHeap 外面的单词数还不到 k 个的时候就加进去;
    b. 或者遇到更高频的单词就把它替换掉。

<span style=”color:orangered;font-weight:bold;”> 时空复杂度剖析:

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

正文完
 0