寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度$latex O(mn)$,计算和$latex mn$,广度优先搜索$latex V+E = mn+(m-1)(n-1)$,速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。[mathjax]
题目
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]
Credits:
Special thanks to @elmirap and @StefanPochmann for adding this problem and creating all test cases.
BFS解法
13ms,算法复杂度O(mn)
从原点开始,不断将带搜索最小值加入优先队列,然后从优先队列取出最小值。和后面一种解法不同,这种解法是利用图的广度优先搜索,下面的解法是DP方式自底向上的搜索。
class Solution { public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { const int n1 = nums1.size(); const int n2 = nums2.size(); vector<pair<int, int>> res; if (k == 0 || n1 == 0 || n2 == 0){ return res; } if (k > n1 * n2){ k = n1 * n2; } vector<vector<bool>> visited(nums1.size(), vector<bool>(nums2.size(), false)); priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; pq.push({ nums1[0]+nums2[0], { 0, 0 } }); visited[0][0] = true; vector<vector<int>> dir{ { 0, 1 }, {0, 1} }; while (k--){ auto t = pq.top(); pq.pop(); int i = t.second.first, j = t.second.second; res.push_back({nums1[i], nums2[j]}); if (j < n2 - 1 && !visited[i][j+1]){ pq.push({ nums1[i] + nums2[j+1], { i, j + 1 } }); visited[i][j + 1] = true; } if (i < n1 - 1 && !visited[i+1][j]){ pq.push({ nums1[i+1] + nums2[j], {i+1, j} }); visited[i + 1][j] = true; } } return res; } };
DP解法
动态规划的方法,也是搜索,13ms,看着很简洁。和我后面那篇博客中丑数的解法类似,就是从最小开始,递进的搜索。因为每个最小的组合都可有之前的最小组合推演得到,先引入一个index来记录num1取不同位置时,之前最小值对应的num2位置,然后根据num2进行搜索就可以了
$$sum(t) = \min_{i<nums1.size}{(nums1(i)+num2(index(i)))}$$
据此进行动态规划,对于新的最小值,只需要更新index表就可以了。DP的核心就是第二个for循环了,在这里是要遍历每一个组合的。
class Solution { public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { const int len1 = nums1.size(), len2 = nums2.size(), cnt = min(k, len1*len2); vector<int> index(len1, 0); vector<pair<int, int>> ans; while(cnt-- > 0) { int temMin = INT_MAX, m = 0; for(int i =0; i < len1; i++) if(index[i] < len2 && nums1[i]+nums2[index[i]] < temMin) temMin= nums1[i]+nums2[index[i]], m = i; ans.push_back(make_pair(nums1[m], nums2[index[m]++])); } return ans; } };