【leetcode】Top-k问题

目录

1. 面试题 17.14. 最小K个数

解题思路

2. 前 K 个高频元素

解题思路

3. 前K个高频单词

解题思路

1. 面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4

输出： [1,2,3,4]

解题思路

1. 改造JDK的最小堆为此时的最"大"堆(存放的是最小k个值，堆顶为最小k个值中的最大值）

        正常的升序即this - o 认为大的大， 反向 o - this 认为小的大

        o1（this) - o2：

                > 0 => o1 > o2

                =0 => o1 == o2

                <0 => o1 < o2

        o2 - o1（this) ：

                > 0 => o1 < o2

                =0 => o1 == o2

                <0 => o1 > o2

2. 将数组中的元素依次入最大堆：堆中的元素小于k时正常入堆；堆中的元素大于k时，将堆顶poll（保证堆中只有k个值）

3. 此时队列中保存了最小的k个数字，将堆中的元素依次poll到要返回的数组中

public int[] smallestK(int[] arr, int k) {// 1.改造JDK的最小堆为此时的最"大"堆Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});for (int i : arr) {queue.offer(i);if (queue.size() > k) {queue.poll();}}// 此时队列中保存了最小的k个数字int[] result = new int[k];for (int i = 0; i < k; i++) {result[i] = queue.poll();}return result;}

2. 前 K 个高频元素

OJ：前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

示例 2:

输入: nums = [1], k = 1 输出: [1]

解题思路

使用Map接口（Map是一个接口类，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。）

times.getOrDefault(nums[i],0)：返回 key 对应的 value，key 不存在，返回默认值

1. 扫描nums数组，将每个元素和出现的次数保存到Map接口中

2. 扫描Map接口，将出现频次最高的前k个Freq对象保存到优先级队列中

3. 从队列中取出这k个Freq的key值就是最终的结果

public int[] topKFrequent(int[] nums, int k) {
//        局部内部类class Freq {int key;// 出现的元素int times;//出现的频率Freq(int key, int value) {this.key = key;this.times = value;}}// 1.扫描nums数组，将每个元素和出现的次数保存到Map接口中Map<Integer,Integer> times = new HashMap<>();for (int i = 0; i < nums.length; i++) {times.put(nums[i],times.getOrDefault(nums[i],0)+1);}Queue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {@Overridepublic int compare(Freq o1, Freq o2) {return o1.times - o2.times;}});// 2.扫描Map接口，将出现频次最高的前k个Freq对象保存到优先级队列中for (Map.Entry<Integer,Integer> i: times.entrySet()) {
//            queue.offer(i);queue.offer(new Freq(i.getKey(),i.getValue()));if(queue.size() > k){queue.poll();}}// 3.从队列中取出这k个Freq的key值就是最终的结果int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll().key;}return ret;}

3. 前K个高频单词

OJ：前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2

输出: ["i", "love"]

解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4

输出: ["the", "is", "sunny", "day"]

解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。

解题思路

1. 扫描nums数组，将每个元素和出现的次数保存到Map接口中

2. 扫描Map接口，将出现频次最高的前k个String保存到优先级队列（小堆)中

3. 从队列中取出这k个String使用头插放入ret链表中（使用头插是因为需要按单词出现频率由高到低排序，每次将队头放入链表的第一个）

4. 返回ret

public List<String> topKFrequent(String[] words, int k) {Map<String,Integer> map = new HashMap<>();for (String str:words) {map.put(str,map.getOrDefault(str,0) + 1);}
//        取大用小Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {int o1times = map.get(o1);int o2times = map.get(o2);return o1times == o2times ? o2.compareTo(o1) : o1times - o2times;}});for (Map.Entry<String,Integer> i: map.entrySet()) {
//            queue.offer(i);queue.offer(i.getKey());if(queue.size() > k){queue.poll();}}//        List没有头插（数组），LinkedList（链表）才有LinkedList<String> ret = new LinkedList<>();while (!queue.isEmpty()){ret.addFirst(queue.poll());}return ret;}