day99（2.28）——leetcode面试经典150

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

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

这题其实有更快的方法，就是可以先把所有（i,0）加入初始根堆，再根据根顶元素得到根顶元素的下一个元素（i,j+1），或者在循环过程中顺带将(i+1,0)和(i,j+1)加入队列中。

这两种方法不会重复，但我写的方法会有重复，所以我创建了一个哈希来去重

题目：

题解：

class Solution { // 编码函数：将 (i, j) 映射为唯一 long // 注意：base 必须大于 j 的最大可能值 (即 nums2.length) private long encode(int i, int j, int base) { return (long) i * base + j; } public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { //创建小根堆 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0]-b[0]); //创建res List<List<Integer>> res = new ArrayList<>(); //这里不需要特断，因为1 <= nums1.length, nums2.length <= 10^5 //将0,0入根堆 pq.offer(new int[]{nums1[0]+nums2[0], 0, 0}); // 哈希表：存储编码后的 long 值 Set<Long> visited = new HashSet<>(); visited.add(encode(0, 0, nums2.length)); // 用列宽 nums2.length 作为基数/100000这样的大常数 while(k-->0&&pq.size()>0) { //获取当前的最小序对 int[] d = pq.poll(); int l = d[1]; int r = d[2]; Long e1 = encode(l+1, r, nums2.length); Long e2 = encode(l, r+1, nums2.length); //判断左右数组各移动一个有什么变化 //类似于bfs搜索 if(l+1<nums1.length && !visited.contains(e1)) { //加入小根堆 pq.offer(new int[]{nums1[l+1]+nums2[r], l+1, r}); //将找到的元素加入映射对象中 visited.add(e1); } if(r+1<nums2.length && !visited.contains(e2)) { //加入小根堆 pq.offer(new int[]{nums1[l]+nums2[r+1], l, r+1}); //将找到的元素加入映射对象中 visited.add(e2); } res.add(List.of(nums1[l],nums2[r])); } return res; } }