九、堆

9.1数据流的第K大数值

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：

• [“KthLargest”, “add”, “add”, “add”, “add”, “add”]
• [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
• 输出：
• [null, 4, 5, 5, 8, 8]

解释：

• KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
• kthLargest.add(3); // return 4
• kthLargest.add(5); // return 5
• kthLargest.add(10); // return 5
• kthLargest.add(9); // return 8
• kthLargest.add(4); // return 8

提示：

• 1 <= k <= 10^4
• 0 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• -10^4 <= val <= 10^4
• 最多调用 add 方法 10^4 次
• 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

思路：优先队列，维护一个k大小的队列，队列第一个元素就是第k大的元素

class KthLargest {int idx;PriorityQueue queue;public KthLargest(int k, int[] nums) {queue = new PriorityQueue<>();idx = k;for (int num : nums) {queue.offer(num);}while (queue.size() > k){queue.poll();}}public int add(int val) {queue.offer(val);while(queue.size() > idx) queue.poll();return  queue.peek();}
}

9.2 出现频率最高的k个数字

原题链接

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

示例 1:

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

提示：

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**思路：**使用map统计每个数出现的次数，借助优先级队列实现小顶堆，维护k大小的窗口

注意点： 需要自定义排序规则

class Solution {public int[] topKFrequent(int[] nums, int k) {Map map = new HashMap<>();for (int num : nums) {map.put(num,map.getOrDefault(num,0)+1);}PriorityQueue queue = new PriorityQueue<>((a,b) -> a[1] - b[1]);for(int key : map.keySet()){int value = map.get(key);if(queue.size() == k){if(queue.peek()[1] < value){queue.poll();queue.offer(new int[]{key,value});}}else{queue.offer(new int[]{key,value});}}int[] res = new int[k];for (int i = 0; i < k; i++) {res[i] = queue.poll()[0];}return res;}
}

9.3和最小的k个数对

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: 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]

提示:

• 1 <= nums1.length, nums2.length <= 10^4
• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1, nums2 均为升序排列
• 1 <= k <= 1000

思路： 优先级队列，将两个数组的下标存入数组中，利用优先级队列对每一数对之和进行从小到大的排序

注意点： 由于可能有重复数字，因此使用数组下标代替数值

class Solution {public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueue queue = new PriorityQueue<>( (a,b) ->{return (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]);});int n = nums1.length;int m = nums2.length;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {queue.offer(new int[]{i,j});}}List> res = new ArrayList<>();for (int i = 0; i < k; i++) {List list = new ArrayList<>();int[] poll = queue.poll();// 防止空指针异常if(poll == null) break;list.add(nums1[poll[0]]);list.add(nums2[poll[1]]);res.add(list);}return res;}
}