https://leetcode.com/problems/find-k-pairs-with-smallest-sums/?tab=Description
给两个升序数组，找到和最小的k个pair
建一个堆，和最小的k个对最多在nums1中包含前k个元素，先把nums1的0 ~ k - 1和nums2的0配对的加到堆里面然后再poll，把poll出来的nums2的后一位和nums1的当前位加到堆里面
public class Solution { public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>(new Comparator<Tuple>() { public int compare(Tuple t1, Tuple t2) { return t1.val - t2.val; } }); List<int[]> res = new LinkedList(); if (nums1.length == 0 || nums2.length == 0 || k == 0) { return res; } for (int i = 0; i < nums1.length && i < k; i++) { queue.add(new Tuple(i, 0, nums1[i] + nums2[0])); } while (k-- > 0 && !queue.isEmpty()) { Tuple t = queue.poll(); res.add(new int[]{nums1[t.x], nums2[t.y]}); if (t.y == nums2.length - 1) { continue; } queue.offer(new Tuple(t.x, t.y + 1, nums1[t.x] + nums2[t.y + 1])); } return res; } class Tuple { int x; int y; int val; public Tuple(int x, int y, int val) { this.x = x; this.y = y; this.val = val; } } }