首页 > 代码库 > Find K Pairs with Smallest Sums -- LeetCode
Find K Pairs with Smallest Sums -- LeetCode
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]思路：这个题目需要转化一下。我们构建一个二维矩阵matrix，matrix[i][j]=nums1[i] + nums2[j]。
例如：对于nums1=[1, 7, 11], nums2=[2, 4, 6]，矩阵matrix是这样子：
2 4 6 +------------ 1 | 3 5 7 7 | 9 11 1311 | 13 15 17因为nums1和nums2都是有序的，因此matrix里每一行都是从小到大，每一列也是从小到大。
那么这个题就变成了，在这个矩阵中找前k小的数。我们用最小堆可以解决这个问题。
首先，左上角的matrix[0][0]肯定是最小的。我们将它放入堆中，作为seed。
之后，我们对这个堆做K次操作：
- 从堆顶取出最小的数，判断它在矩阵中的行和列（可以用tuple实现），将对应的nums1和nums2的两个数构造成pair添加进结果。
- 若取出的数不在矩阵最后一列，则将该行它的下一个数放入堆中。
- 若取出的数在矩阵第一列，且不在最后一行，则还要将它的下一行行首的数放入堆中。
- 若堆为空，则提前退出循环(没有这么多pair)。
算法复杂度: K次循环，每次循环从堆中取出一个数，最多放入两个数，则堆空间最大为O(K)， push和pop操作复杂度为O(logK)。总时间复杂度为O(KlogK)。
代码心得：tuple类型声明往往比较长，可以用typedef。
1 class Solution { 2 public: 3 vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { 4 vector<pair<int, int> > res; 5 if (!nums1.size() || !nums2.size()) return res; 6 7 typedef tuple<int, int, int> triInt; 8 vector<triInt> heap(1, make_tuple(nums1[0] + nums2[0], 0, 0)); 9 int height = nums1.size(), width = nums2.size();10 while (k-- && heap.size()) {11 triInt top = heap.front();12 std::pop_heap(heap.begin(), heap.end(), greater<triInt>()); heap.pop_back();13 int row = get<1>(top), col = get<2>(top);14 res.push_back(make_pair(nums1[row], nums2[col]));15 if (col < width - 1) {16 heap.push_back(make_tuple(nums1[row] + nums2[col + 1], row, col + 1));17 std::push_heap(heap.begin(), heap.end(), greater<triInt>());18 }19 if (col == 0 && row < height - 1) {20 heap.push_back(make_tuple(nums1[row + 1] + nums2[col], row + 1, col));21 std::push_heap(heap.begin(), heap.end(), greater<triInt>());22 }23 }24 return res;25 }26 };
Find K Pairs with Smallest Sums -- LeetCode
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。