Question:
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 = 3
Return: [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 = 2
Return: [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]
Solution:
class Solution {public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<pair<int,int>> res; if(nums1.empty() || nums2.empty() || k == 0){ return res; } vector<pair<int,int>> tmp; int l1 = nums1.size(); int l2 = nums2.size(); //第一步，将所有可能的pair读入 for(int i = 0 ; i < l1;i++){ for(int j = 0 ; j < l2; j++){ tmp.push_back(make_pair(nums1[i],nums2[j])); } } //构造小顶堆 buildheap(tmp); int ltmp = tmp.size(); for(int i = 0 ; i<k&&i<ltmp;i++){//找到k对或者小顶堆读尽结束 res.push_back(tmp[0]); tmp[0] = tmp.back(); tmp.pop_back(); heap(tmp,0); } return res; } void buildheap(vector<pair<int,int>>& nums){ int len = nums.size(); for(int i = len/2 ; i >= 0;i--){//由中间的位置开始，也就是从最后一个元素开始，将最小数往上冒 heap(nums,i); } } void heap(vector<pair<int,int>>& nums,int i){ int len = nums.size(); int msum = nums[i].first+nums[i].second; int min = i; int l = (i<<1) + 1; int r = l+1; if(l < len && nums[l].first+nums[l].second < msum){ min = l; msum = nums[l].first+nums[l].second; } if(r < len && nums[r].first+nums[r].second < msum){ min = r; }//在该元素和他两个孩子中找到最小 pair<int,int> tmp = nums[min]; nums[min] = nums[i]; nums[i] = tmp;//将最小元素放置在双亲位置 if(min != i){//确保该元素在正确的位置 heap(nums,min); } }};总结： 三个注意点：
起始索引为0的情况，其左右孩子索引为2i+1和2i+2,而不是2i和2i+1!!使用 移位符号时，比如 i<<1+1，注意+优先级大于<<,所以结果为 i 左移 2 位，并非 i 左移 1 位 加 1.构造小顶堆的时候，循环要从len/2递减，而不是由0到len/2递增。第二种情况最终的结果只能保证最大值在叶子节点，并不能保证堆顶是最小值。新闻热点
疑难解答
