[LeetCode]Find K Pairs with Smallest Sums

如果我们将两个数组展开，可以得到一个2D的matrix。例如[1,2,3]和[1,1,2]。我们可以得到下图：

我们可以看出来，这个matrix从左向右，自上而下是递增的。假设有m行，n列，就可以看做m个长度为n的sorted list，那么这个问题也就转变为merge m sorted list and get first k element，那么很明显我们就可以用priority queue来解。我们先把[0, 0]加入优先队列，每次从队列中取出最小的，如果其下边和右边还有元素就将其推入优先队列，直到得到k个元素。循环只有k次，每次我们取出一个最多推入两个，优先队列初始长度为1，所以队列长度<= k。时间按复杂度O(k)，空间复杂度O(k)，代码如下：

另外一点，如果这道题不是求前k个，而是求第k个，我们还可以用值域的二分法来做。例如，Kth Smallest Element in Sorted Array, Find Kth Smallest Pair Distance