堆——算法专项刷题（九）

爱被打了一巴掌 2024-03-31 17:04 40阅读 0赞

### 九、堆 ###

#### 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<Integer> 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个数字 ####

[原题链接][Link 1]

给定一个整数数组 `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<Integer,Integer> map = new HashMap<>();
    
            for (int num : nums) {
        
               map.put(num,map.getOrDefault(num,0)+1);
    
    
            }
    
            PriorityQueue<int[]> 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<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        
    
    
            PriorityQueue<int[]> 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<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < k; i++) {
        
                List<Integer> 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;
    
    
    
        }
    }

[Link 1]: https://leetcode.cn/problems/g5c51o/