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.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Example 1:
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3Return: [1,2],[1,4],[1,6]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:
Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2Return: [1,1],[1,1]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:
Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3]All possible pairs are returned from the sequence:[1,3],[2,3]
Credits:
Special thanks to and for adding this problem and creating all test cases.
这道题给了我们两个数组，让我们从每个数组中任意取出一个数字来组成不同的数字对，返回前K个和最小的数字对。那么这道题有多种解法，我们首先来看brute force的解法，这种方法我们从0循环到数组的个数和k之间的较小值，这样做的好处是如果k远小于数组个数时，我们不需要计算所有的数字对，而是最多计算k*k个数字对，然后将其都保存在res里，这时候我们给res排序，用我们自定义的比较器，就是和的比较，然后把比k多出的数字对删掉即可，参见代码如下：
解法一：
class Solution {public: vector > kSmallestPairs(vector & nums1, vector & nums2, int k) { vector > res; for (int i = 0; i < min((int)nums1.size(), k); ++i) { for (int j = 0; j < min((int)nums2.size(), k); ++j) { res.push_back({nums1[i], nums2[j]}); } } sort(res.begin(), res.end(), [](pair &a, pair &b){ return a.first + a.second < b.first + b.second;}); if (res.size() > k) res.erase(res.begin() + k, res.end()); return res; }};
我们也可以使用multimap来做，思路是我们将数组对之和作为key存入multimap中，利用其自动排序的机制，这样我们就可以省去sort的步骤，最后把前k个存入res中即可：
解法二：
class Solution {public: vector > kSmallestPairs(vector & nums1, vector & nums2, int k) { vector > res; multimap > m; for (int i = 0; i < min((int)nums1.size(), k); ++i) { for (int j = 0; j < min((int)nums2.size(), k); ++j) { m.insert({nums1[i] + nums2[j], {nums1[i], nums2[j]}}); } } for (auto it = m.begin(); it != m.end(); ++it) { res.push_back(it->second); if (--k <= 0) return res; } return res; }};
下面这种方式用了priority_queue，也需要我们自定义比较器，整体思路和上面的没有什么区别：
解法三：
class Solution {public: vector > kSmallestPairs(vector & nums1, vector & nums2, int k) { vector > res; priority_queue , vector >, cmp> q; for (int i = 0; i < min((int)nums1.size(), k); ++i) { for (int j = 0; j < min((int)nums2.size(), k); ++j) { if (q.size() < k) { q.push({nums1[i], nums2[j]}); } else if (nums1[i] + nums2[j] < q.top().first + q.top().second) { q.push({nums1[i], nums2[j]}); q.pop(); } } } while (!q.empty()) { res.push_back(q.top()); q.pop(); } return res; } struct cmp { bool operator() (pair &a, pair &b) { return a.first + a.second < b.first + b.second; } };};
下面这种方法比较另类，我们遍历nums1数组，对于nums1数组中的每一个数字，我们并不需要遍历nums2中所有的数字，实际上，对于nums1中的数字，我们只需要记录nums2中下一个可能组成数字对的坐标，这里我们使用一个idx数组，其中idx[i]表示的数字是nums1[i]将从nums2数组上开始寻找的位置，因为 {nums1[i], nums2[i - 1]} 已经被加入到了结果res中，这种方法其实也是一种地毯式搜索，但是并不需要遍历完所有的组合，因为我们有idx数组来进行剪枝。我们suppose需要进行k次循环，但是题目中没有说我们一定能取出k对数字，而我们能取出的对儿数跟数组nums1和nums2的长度有关，最多能取出二者的长度之积的对儿数，所以我们取其跟k之间的较小值为循环次数。我们定义idx数组，长度为nums1的长度，初始化均为0。下面开始循环，在每次循环中，我们新建变量cur，记录从nums1中取数的位置，初始化为0，使用变量sum来记录一个当前最小的两数之和，初始化为正无穷。然后开始遍历数组nums1，更新sum的条件有两个，第一个是idx[i]上的数要小于nums2的长度，因为其是在nums2开始寻找的位置，当然不能越界，第二个条件的候选的两个数组 nums1[i] 和 nums2[idx[i]] 之和小于等于sum。同时满足这两个条件就可以更新sum了，同时更新cur为i，表示当前从nums1取出数字的位置。当遍历nums1的for循环结束后，此时cur的位置就是要从nums1取出的数字的位置，根据idx[cur]从nums2中取出对应的数组，形成数对儿存入结果res中，然后idx[cur]自增1，因为当前位置的数字已经用过了，下次遍历直接从后面一个数字开始吧，这是本解法的设计精髓所在，一定要弄清楚idx数组的意义，参见代码如下：
解法四：
class Solution {public: vector > kSmallestPairs(vector & nums1, vector & nums2, int k) { vector > res; int size = min(k, int(nums1.size() * nums2.size())); vector idx(nums1.size(), 0); for (int t = 0; t < size; ++t) { int cur = 0, sum = INT_MAX; for (int i = 0; i < nums1.size(); ++i) { if (idx[i] < nums2.size() && sum >= nums1[i] + nums2[idx[i]]) { cur = i; sum = nums1[i] + nums2[idx[i]]; } } res.push_back({nums1[cur], nums2[idx[cur]]}); ++idx[cur]; } return res; }};
参考资料：