###### tags: `Leetcode` `medium` `heap` `python` `c++`

# 373. Find K Pairs with Smallest Sums

## [題目連結:] https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

## 題目:
You are given two integer arrays ```nums1``` and ```nums2``` sorted in **ascending order** and an integer ```k```.

Define a pair ```(u, v)``` which consists of one element from the first array and one element from the second array.

Return the ```k``` pairs ```(u1, v1), (u2, v2), ..., (uk, vk)``` with the smallest sums.

**Example 1:**

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

**Example 2:**

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

**Example 3:**

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

## 解題想法:
* 此題為，給num1、num2皆為由小到大排序
* return 前k個最小和的pair(u,v)
* u: from nums1
* v: from nums2

* 使用heap queue進行儲存:
* Step1:
* **將nums1中每個元素與nums2[0]匹配存於queue**
* 儲存的pair **(總和, pos in nums1, pos in nums2)**
* Step2:
* 因為ex3，題目表明k有可能大於len(nums1) * len(nums2)的總長
* while len(res)< min(k, len(nums1) * len(nums2)):

* Step3: while中進行判斷
* 每次heappop最小的存於res
* sum,i,j=heapq.heappop(heap)
* i=pos in nums1
* j=pos in nums2
* 最後需要判斷: if j+1<len(nums2):
* heappush(heap,(nums1[i]+nums2[j+1],i,j+1))
* 因為: i很小立了大功 看看其他j有沒有機會分杯羹

## Python:

from heapq import heappush, heappop
class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        que=[]
        #將nums1中每個元素與nums2[0]匹配存於que
        #(總和,pos in nums1, pos in nums2)
        for pos,val in enumerate(nums1):
            heappush(que,(val+nums2[0], pos, 0)) #由總和小至大
        res=[]
        #填滿res
        while len(res)< min(k, len(nums1)*len(nums2)):
            curSum, i, j=heappop(que)
            res.append([nums1[i], nums2[j]])
            if j+1<len(nums2): #i很小立了大功 看看其他j有沒有機會分杯羹
                heappush(que,(nums1[i]+nums2[j+1], i, j+1))
        return res

## c++:

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int len1=nums1.size(), len2=nums2.size();
        //max_heap
        priority_queue<vector<int>> que;
        for (int pos1=0; pos1<len1; pos1++){
            que.push({-(nums1[pos1]+nums2[0]), pos1, 0});
        }
        vector<vector<int>> res;
        while (res.size()< k){
            //while 判斷改成 res.size()< min(k, len1*len2) 會發生signed integer overflow: 99994 * 99998 cannot be represented in type 'int' (solution.cpp) :"(
            if (que.empty())  //所以直接用判斷que是否為空跳出while進行判斷 就可以通過了
                break;
            vector<int> curItem=que.top(); que.pop();
            int i=curItem[1], j=curItem[2];
            res.push_back({nums1[i], nums2[j]});
            if (j+1<len2)
                que.push( {-(nums1[i]+nums2[j+1]), i, j+1});
        }
        return res;
    }
};