373. Find K Pairs with Smallest Sums

Version #1 MinHeap with Lambda

41.23 %
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> result = new ArrayList<>();
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return result;
        // minHeap -> always poll out the minimum sum and add its adjacent sums
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(10, (pairA, pairB) ->
                                                           (nums1[pairA[0]] + nums2[pairA[1]]) - (nums1[pairB[0]] + nums2[pairB[1]]));
        minHeap.offer(new int[]{0, 0});
        while (k-- > 0 && !minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int i1 = curr[0];
            int i2 = curr[1];
            result.add(new int[]{nums1[i1], nums2[i2]});
            if (i1 == 0 && (i2 + 1 < nums2.length)) minHeap.offer(new int[]{i1, i2 + 1});
            if (i1 + 1 < nums1.length) minHeap.offer(new int[]{i1 + 1, i2});
        }
     
        return result;
    }
}

Version #2 Self-defined  class -> Tuple with is own compareTo method
LC上看到的，拿过来做reference
如果lambda写不好可以参考这个方法
92.17 %

"public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(); int m = nums1.length, n = nums2.length; List<int[]> res = new ArrayList<int[]>(); if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res; for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j])); for(int i = 0; i < Math.min(k, m *n); i++) { Tuple t = pq.poll(); res.add(new int[]{nums1[t.x], nums2[t.y]}); if(t.x == m - 1) continue; pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y])); } return res; } } class Tuple implements Comparable<Tuple> { int x, y, val; public Tuple (int x, int y, int val) { this.x = x; this.y = y; this.val = val; } @Override public int compareTo (Tuple that) { return this.val - that.val; } }"