lc373 Find K Pairs with Smallest Sums该用最大还是最小堆的问题

首先我的思路是，用最大堆，当比k个多元素的时候，就poll出去，留下的自然是最小的
这是我的代码：

1. public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k){
   
2.         List<List<Integer>> res= new ArrayList<>();
   
3.         //corner case
   
4.         PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)->b[0]+b[1]-a[0]-a[1]);
   
5.         
   
6.         for(int nums:nums1){
   
7.             maxHeap.offer(new int[]{nums,nums2[0],0});
   
8.             
   
9.             if(maxHeap.size()>k){
   
10.                 maxHeap.poll();
    
11.             }
    
12.         }
    
13.         //再倒出来
    
14.         while(!maxHeap.isEmpty() && k-->0){
    
15.             int [] cur=maxHeap.poll();
    
16.             res.add(Arrays.asList(cur[0],cur[1]));
    
17.             
    
18.             if(cur[2]==nums2.length-1) continue;
    
19. 
    
20.             maxHeap.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
    
21.         }
    
22.         return res;

复制代码

然而，当test case 为：
[1,1,2]
[1,2,3]
2
的时候，我的结果[[1,1],[2,1]]和答案不同：[[1,1],[1,1]]
然后看到一个正确的答案代码，用的minHeap，我觉得其他代码也一样：

1. public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
   
2.                 List<List<Integer>> res = new ArrayList<>();
   
3.         if (nums1.length == 0 || nums2.length == 0 || k == 0) {
   
4.             return res;
   
5.         }
   
6. 
   
7.         PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[0] + a[1] - b[0] - b[1]));
   
8.         for (int i = 0; i < nums1.length && i < k; i++) {
   
9.             minHeap.offer(new int[]{nums1[i], nums2[0], 0});
   
10.         }
    
11. 
    
12.         while (!minHeap.isEmpty() && k-- > 0) {
    
13.             int[] cur = minHeap.poll();
    
14.             res.add(Arrays.asList(cur[0],cur[1]));
    
15.             if (cur[2] == nums2.length - 1) continue;
    
16.             minHeap.offer(new int[]{cur[0], nums2[cur[2] + 1], cur[2] + 1});
    
17.         }
    
18.         return res;
    
19.     }

复制代码

这个运行结果就正确，不知为何
望指教

今天也刚好复习这个题，刚好回忆一下思路。
首先一开始自己的brute force就是利用nums1和nums2得到相应的pair然后放入k size的最大堆中，然后最后留下来的就是最小的k个pair。但是这个time: O(NlogK)
然后其实可以想为啥不能先遍历完 nums1中一个数与nums2所有的pair 然后和k作比较呢？ （这里其实就和楼主的代码一样，先放入了k个 nums1[i], nums2[0]这样的pair。因为其实这样是保持了最小的情况。
所以我用最小堆，作为每次poll() 之后加入结果集中。之后只要没有nums1[i] 没有遍历完nums2的个数，就会把下一个candidate 加入
即

1. if (cur.get(2) == nums2.length - 1) continue;
   
2.             // 加入下一个nums2
   
3.             pq.offer(new ArrayList<>(Arrays.asList(cur.get(0), nums2[cur.get(2) + 1], cur.get(2) + 1)));

复制代码

所以这样就可以得到结果了。 楼主应该是有点困惑，求k个最小就应该用 max heap吗？
但注意了，之前这种情况 往往是你有n个 candidate， 然后维护k个大小的pq。然后你遍历完n个，需要把大的都删除掉，所以用max heap。
而这里我们选择加入res的地方，是在poll()的时候，所以应该用min heap保持最小在第一个poll出来。
以上是我的理解，如有错误，欢迎讨论。

akdhfikbk 发表于 2020-2-3 09:35
所以这题只能用最小堆，而且写法非常固定的亚子
我想通了用最小堆之后，我还想保留for(int num:nums1){/ ...

14行那个block，假如nums的长度大于k，你此时不能保证nums2的第一个元素跟nums1第1个后面的元素相加是我们想要的答案，但是你16行，赤裸裸的加进去了。
所以如果用minHeap，那么就只加入小于等于k个元素进去就行了.
如果用maxHeap，那么要双循环把所有的pair都加进queue

15行不能保证是我们想要的结果，你想想为什么？

1点50分 发表于 2020-2-3 08:18
15行不能保证是我们想要的结果，你想想为什么？

因为是最大的...

1点50分 发表于 2020-2-3 08:18
15行不能保证是我们想要的结果，你想想为什么？

所以这题只能用最小堆，而且写法非常固定的亚子
我想通了用最小堆之后，我还想保留for(int num:nums1){//逻辑}部分，发现还是不可以

1. class Solution {
   
2.     public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k){
   
3.         List<List<Integer>> res= new ArrayList<>();
   
4.         //corner case
   
5.         if (nums1.length == 0 || nums2.length == 0 || k == 0) {
   
6.             return res;
   
7.         }
   
8.         //minHeap now
   
9.         PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]-b[1]);
   
10.         
    
11.         for(int nums:nums1){
    
12.             minHeap.offer(new int[]{nums, nums2[0], 0});
    
13.             
    
14.             if(minHeap.size()>k){
    
15.                 int[] min=minHeap.poll();
    
16.                     res.add(Arrays.asList(min[0],min[1]));
    
17.                 // k--;
    
18.             }
    
19.             k--;
    
20.         }
    
21.         //再倒出来
    
22.         //--k也不可
    
23.         while(!minHeap.isEmpty() && k-->0){
    
24.             // k--; //逻辑还是不通，个数还是保证不了
    
25.             int [] cur=minHeap.poll();
    
26.             res.add(Arrays.asList(cur[0],cur[1]));
    
27.             
    
28.             if(cur[2]==nums2.length-1) continue;
    
29.             minHeap.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
    
30.         }
    
31.         return res;
    
32.     }
    
33. }

复制代码

input:
[1,2,4,5,6]
[3,5,7,9]
3
Output:[[1,3],[2,3],[4,3]]
Expected:[[1,3],[2,3],[1,5]]

1点50分 发表于 2020-2-3 10:43
14行那个block，假如nums的长度大于k，你此时不能保证nums2的第一个元素跟nums1第1个后面的元素相加是我 ...

所以这道题的写法还蛮固定的
或者说，把蛮字去掉
有且只有一种写法