topk算法-leetcode java题解

• topk算法-leetcode java题解
  • java优先队列
  • leetcode Num17.14:找数组中最小k个数
  • leetcode Num347:前k个高频元素
  • leetcode 373. 查找和最小的 K 对数字
  • leetcode 692. 前K个高频单词
  • leetcode 1046. 最后一块石头的重量
  • 参考链接

java优先队列

PriorityQueue(优先队列），一个基于优先级堆的无界优先级队列。

通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。

PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加

小顶堆

//默认容量为11
PriorityQueue minHeap = new PriorityQueue();//小根堆实例
PriorityQueue heap = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Integer o1, Integer o2){return o1 - o2;}
});// 将数组元素放入堆
int[] arr = {6,5,2,3,1,4};for (int i :arr) {heap.offer(i);
}
System.out.println(heap);int index = 0;
// 每次将堆顶元素放入数组，并删除堆顶元素，相当于每次从剩余堆中取最大值
for (int i = 0; i < arr.length; i++) {arr[index++] = (Integer) heap.poll();
}for (int i :arr) {System.out.print(i + " ");  // 1 2 3 4 5 6 
}

可能的初始化形式

// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue queue = new PriorityQueue(new Comparator() {public int compare(int[] m, int[] n) {return m[1] - n[1];}
});PriorityQueue> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());

大顶堆

//容量11 
PriorityQueue maxHeap = new PriorityQueue(11,new Comparator(){@Overridepublic int compare(Integer i1,Integer i2){return i2 - i1;}
});
//大顶堆实例
PriorityQueue queue = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Student o1, Student o2){return o2.getId() - o1.getId();}
});

取最小的N个数：使用大顶堆
先出大数：使用大顶堆

取最大的N个数：使用小顶堆
先出小数：使用小顶堆

常用方法

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出nullpublic boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator iterator(); //迭代器

leetcode Num17.14:找数组中最小k个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

找出数组中最小的k个数。以任意顺序返回这k个数均可（取小数用大堆）

    public int[] smallestK(int[] arr, int k) {if(arr.length == 0|| k == 0){return new int[0];}PriorityQueue queue = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});for(int i : arr){if(queue.size() < k){queue.offer(i);}else{int peek = queue.peek();if(i > peek){//元素>堆顶元素，不入队，进入下一个循环continue;}else{queue.poll();queue.offer(i);}}}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

leetcode Num347:前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

参数为int

    public int[] topKFrequent(int[] nums, int k) {Map map = new HashMap<>();for(int i : nums){if(map.containsKey(i)){int num = map.get(i) + 1;map.put(i,num);}else {map.put(i,1);}}// 遍历map，用最小堆保存频率最大的k个元素PriorityQueue pq = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Integer a, Integer b) {return map.get(a) - map.get(b);}});for (Integer key : map.keySet()) {if (pq.size() < k) {pq.add(key);} else if (map.get(key) > map.get(pq.peek())) {pq.remove();pq.add(key);}}int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = pq.poll();}return res;}

参数为int[]

class Solution {public int[] topKFrequent(int[] nums, int k) {Map occurrences = new HashMap();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数PriorityQueue queue = new PriorityQueue(new Comparator() {public int compare(int[] m, int[] n) {return m[1] - n[1];}});for (Map.Entry entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0];}return ret;}
}

新建参数的实体类

class Solution {/*** 利用优先队列* 小根堆，顶部为第k个大*/class Pair {int value;  //存储的元素int freq;   //元素出现的频次Pair(int value, int freq) {this.value = value;this.freq = freq;}}public int[] topKFrequent(int[] nums, int k) {Map map = new HashMap<>();for (int d : nums) {map.put(d, map.getOrDefault(d, 0) + 1);}PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器@Overridepublic int compare(Pair o1, Pair o2) {return o1.freq - o2.freq;}});for (Map.Entry entry : map.entrySet()) {if (queue.size() == k) {if (entry.getValue() > queue.peek().freq) {queue.poll();queue.add(new Pair(entry.getKey(), entry.getValue()));}} else {queue.add(new Pair(entry.getKey(), entry.getValue()));}}int[] ret = new int[k];//此时,最小堆内的元素就是需要的元素，依次出队for (int i = 0; i < k; i++) {ret[i] = queue.poll().value;}return ret;}}

leetcode 373. 查找和最小的 K 对数字

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

• 方式一：结果为堆中元素

  对于单个序列的TopK问题，首先将序列的前 k 个元素添加到大根堆(降序)中
  然后遍历剩下的 n - k 个元素，逐个判断其与堆顶元素的大小，当前元素小时，取出堆顶，加入当前元素(堆调整)
  最终堆中剩余的 k 个元素就是TopK

• 方式二：结果为堆中每次取出的元素

  对于多个序列的TopK问题，如本题是有两个独立的数组，需要先对各个子序列排序
  接着同样在小根堆(升序)中维护对应序列个数个元素，然后每次取出堆顶元素，并加入当前堆顶元素(最小值)所在序列的下一个值，一共进行 k 次
  取出的元素组成的集合( k 个)就是TopK，这种方式也成为多路归并，常见于大文件排序、海量数据排序等场景(面试热点)

（1）结果为堆中元素

    public static List> kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器@Overridepublic int compare(Pair o1, Pair o2) {return (o2.n1 + o2.n2) - (o1.n1 + o1.n2);}});for (int i = 0; i < Math.min(nums1.length,k); i++) {for (int j = 0; j < Math.min(nums2.length,k); j++) {if(queue.size() < k){queue.offer(new Pair(nums1[i],nums2[j]));}else {int sum = nums1[i] + nums2[j];Pair pair = queue.peek();if(sum < pair.n1 + pair.n2){queue.poll();queue.offer(new Pair(nums1[i], nums2[j]));}}}}List> ret = new ArrayList<>();for (int i = 0; i < k && (!queue.isEmpty()); i++) {List temp = new ArrayList<>();Pair pair = queue.poll();temp.add(pair.n1);temp.add(pair.n2);ret.add(temp);}return ret;}static class Pair{//第一个数组的值int n1;//第二个数组的值int n2;Pair(int n1, int n2) {this.n1 = n1;this.n2 = n2;}}

（2）结果为堆中每次取出的元素

    public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {// 优先级队列，保存 [index1, index2]PriorityQueue heap = new PriorityQueue<>(new Comparator() {//传入比较器@Overridepublic int compare(int[] o1, int[] o2) {return (nums1[o1[0]] + nums2[o1[1]]) - (nums1[o2[0]] - nums2[o2[1]]);}});// 把 nums1 的所有索引入队，nums2 的索引初始时都是 0for (int i = 0; i < Math.min(k, nums1.length); i++) {heap.offer(new int[] {i, 0});}List> ans = new ArrayList<>();while (k-- > 0 && !heap.isEmpty()) {int[] pos = heap.poll();List list = new ArrayList<>();list.add(nums1[pos[0]]);list.add(nums2[pos[1]]);ans.add(list);if (pos[1] + 1 < nums2.length) {heap.offer(new int[]{pos[0], pos[1] + 1});}}return ans;} 

leetcode 692. 前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。注意，按字母顺序 "i" 在 "love" 之前。

相等次数的值的顺序比较，按照字母
x.compareTo(y)，y大返回1

    public List topKFrequent(String[] words, int k) {// 1.先用哈希表统计单词出现的频率Map count = new HashMap();for (String word : words) {count.put(word, count.getOrDefault(word, 0) + 1);}// 2.构建小根堆 这里需要自己构建比较规则 此处为 lambda 写法 Java 的优先队列默认实现就是小根堆PriorityQueue minHeap = new PriorityQueue<>((s1, s2) -> {if (count.get(s1).equals(count.get(s2))) {return s2.compareTo(s1);} else {return count.get(s1) - count.get(s2);}});// 3.依次向堆加入元素。for (String s : count.keySet()) {minHeap.offer(s);// 当堆中元素个数大于 k 个的时候，需要弹出堆顶最小的元素。if (minHeap.size() > k) {minHeap.poll();}}// 4.依次弹出堆中的 K 个元素，放入结果集合中。List res = new ArrayList(k);while (minHeap.size() > 0) {res.add(minHeap.poll());}// 5.注意最后需要反转元素的顺序。Collections.reverse(res);return res;}        

    public List topKFrequent(String[] words, int k) {Map map = new HashMap<>();for (String d : words) {map.put(d, map.getOrDefault(d, 0) + 1);}PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器@Overridepublic int compare(Pair s1, Pair s2) {if (s1.freq == s2.freq) {// 如果指定的数与参数相等返回 0return s2.value.compareTo(s1.value);} else {return s1.freq - s2.freq;}}});for (Map.Entry entry : map.entrySet()) {queue.offer(new Pair(entry.getKey(), entry.getValue()));if (queue.size() > k) {queue.poll();}}List res = new LinkedList<>();while (!queue.isEmpty()){res.add(queue.poll().value);}Collections.reverse(res);return res;}static class Pair {String value;  //存储的元素int freq;   //元素出现的频次Pair(String value, int freq) {this.value = value;this.freq = freq;}}

leetcode 1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

要弹出最大的数，用大根堆

    public int lastStoneWeight(int[] stones) {PriorityQueue queue = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});for (int stone : stones) {queue.offer(stone);}while (queue.size() > 1) {int a = queue.poll();int b = queue.poll();if (a > b) {queue.offer(a - b);}}if(queue.isEmpty()){return 0;}else{return queue.poll();}}