LeetCode_373: Find K Pairs with Smallest Sums

寻找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;  
    }  
};

 

发表评论