Find K Pairs with Smallest Sums

给定两个升序整数数组nums1 nums2以及一个整数k。

定义一个数对，一个元素来自nums1 一个来自nums2。

目的是返回k个数对，这些数对的内部元素之和升序存放。

例子如下：

1
2
3
4
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]

解题思路：

  1. 初级思路：求出每一个对，然后再找出前K大的对，返回。
    1. 缺点：时空复杂度都太高。求出每一个对时间复杂度为 $O(m^2)$，找出前K大的对时间复杂度为$O(mlogm)$ 。
  2. 中级思路：使用map容器进行选择。以数对之和为键, 数对数组为值（可能有，map会自动排序，然后输出前k个对。。这种做法结果证明时空占用都挺大的。。
  3. 看看大佬们的分享。使用优先队列来搞，比较快的样子。

…. 最简单的做法， 使用map键的自动排序特性。这个内部实现肯定比直接使用现有高效的排序方式来的慢。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<map>
#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
	vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
		map<int, vector<pair<int, int>>> _map;
		for (auto iter1 = nums1.begin(); iter1 != nums1.end(); iter1++) {
			for (auto iter2 = nums2.begin(); iter2 != nums2.end(); iter2++) {
				int sum = *iter1 + *iter2;
				_map[sum].push_back(make_pair(*iter1, *iter2));
			}
		}
		int num = 0;
		vector<pair<int, int>> res;
		for (auto it = _map.begin(); it != _map.end(); it++) {
			for (auto vec = it->second.begin(); vec != it->second.end(); vec++) {
				res.push_back(*vec);
				num++;
				if (num == k)
					return res;
			}
			if (num == k)
				return res;
		}
		return res;
	}
};


int main() {
	Solution s;
	int arr1[3] = { 1, 7, 13 };
	int arr2[3] = { 2, 4, 8 };
	vector<int> nums1;
	vector<int> nums2;
	for (int i = 0; i < 3; i++) {
		nums1.push_back(arr1[i]);
		nums2.push_back(arr2[i]);
	}
	vector<pair<int, int>> res = s.kSmallestPairs(nums1, nums2, 3);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i].first << " " << res[i].second << endl;
	}
	system("pause");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        if (nums1.empty() || nums2.empty() || k == 0) {
            return {};
        }
        vector<pair<int, int>> result;
        result.reserve(k);
        
        // 定义排序方式
        auto cmp = [&nums1, &nums2](const pair<int, int>& p1, const pair<int, int>& p2) {
            return nums1[p1.first] + nums2[p1.second] > nums1[p2.first] + nums2[p2.second];
        };
        
        // 第一个元素是pair对，第二个元素是pair数组，保证某些和相同的对在同一位置
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        //  ？？？先放数组一的第一个元素进优先队列
        for (int i = 0; i < nums1.size(); ++i) {
            q.push(make_pair(i, 0));
        }
        // 利用优先队列来筛选目标
        while (k-- > 0 && !q.empty()) {
            // 返回队首，由于优先特性，返回的是最小的对
            auto minPair = q.top();
            q.pop();
            if (minPair.second + 1 < nums2.size()) {
                q.push(make_pair(minPair.first, minPair.second + 1));
            }
            // 数组尾部替换为新筛选得到的最小对
            result.emplace_back(nums1[minPair.first], nums2[minPair.second]);
        }
        return result;
    }
};