寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度\(O(mn)\),计算和\(mn\),广度优先搜索\(V+E = mn+(m-1)(n-1)\),速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。

题目

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方式自底向上的搜索。

DP解法

动态规划的方法,也是搜索,13ms,看着很简洁。和我后面那篇博客中丑数的解法类似,就是从最小开始,递进的搜索。因为每个最小的组合都可有之前的最小组合推演得到,先引入一个index来记录num1取不同位置时,之前最小值对应的num2位置,然后根据num2进行搜索就可以了

$$sum(t) = \min_{i<nums1.size}{(nums1(i)+num2(index(i)))}$$

据此进行动态规划,对于新的最小值,只需要更新index表就可以了。DP的核心就是第二个for循环了,在这里是要遍历每一个组合的。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注