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:
- 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]
代码 1:
- class Solution {
- public:
- vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
- vector<pair<int, int>> res;
- multimap<int, pair<int, int>> 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;
- }
- };
- View Code
代码 2:
- class Solution {
- public:
- vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
- vector<pair<int, int>> sum;
- vector<pair<int, int>> ans;
- int N = nums1.size(), M = nums2.size();
- for(int i = 0; i <min(N, k); i ++) {
- for(int j = 0; j < min(M ,k); j ++) {
- ans.push_back({nums1[i], nums2[j]});
- }
- }
- sort(ans.begin(), ans.end(), [](pair<int, int> &a, pair<int, int> &b){return a.first + a.second <b.first + b.second;});
- if (ans.size()> k) ans.erase(ans.begin() + k, ans.end());
- return ans;
- }
- };
- View Code
粗门啦!
- FH
来源: http://www.bubuko.com/infodetail-2945881.html