json做网站的数据库,免费seo在线工具,犀牛云建设网站,游戏官网制作文章目录 题目描述解题思路代码 题目链接 题目描述
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)#xff0c;其中第一个元素来自 nums1#xff0c;第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (… 文章目录 题目描述解题思路代码 题目链接 题目描述
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
输入: nums1 [1,7,11], nums2 [2,4,6], k 3 输出: [1,2],[1,4],[1,6] 解释: 返回序列中的前 3 对数 [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] 示例 2:
输入: nums1 [1,1,2], nums2 [1,2,3], k 2 输出: [1,1],[1,1] 解释: 返回序列中的前 2 对数 [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
提示:
1 nums1.length, nums2.length 105 -109 nums1[i], nums2[i] 109 nums1 和 nums2 均为 升序排列 1 k 104 k nums1.length * nums2.length
解题思路
参考
多路归并的方法来解决这个问题因为我们是找前k个最小的数那么我们可以这样来 令 nums1 的长度为 nnums2 的长度为 m所有的点对数量为 n×m。
其中每个 nums1[i] 参与所组成的点序列为
[(nums1[0],nums2[0]),(nums1[0],nums2[1]),…,(nums1[0],nums2[m−1])] [(nums1[1],nums2[0]),(nums1[1],nums2[1]),…,(nums1[1],nums2[m−1])] [(nums1[n−1],nums2[0]),(nums1[n−1],nums2[1]),…,(nums1[n−1],nums2[m−1])] 由于 nums1 和 nums2 均已按升序排序因此每个 nums1[i] 参与构成的点序列也为升序排序这引导我们使用「多路归并」来进行求解。
怎么做呢 既然是多路排序那就是把以前的二路排序扩展一下现在我们使用n路排序我们按照上面的分法就可以把序列分成n行然后我们可以在这n行中每次选最小的一个就好啦这样选k次就是我们要的答案了。 具体怎么实现呢 我们其实的时候买把这n个序列的第一个元素以二元组i,j入队优先队列或者是小根堆其中 i 为该点对中 nums1[i] 的下标j 为该点对中 nums2[j]的下标这里可以有一个小优化我们始终确保nums1为两数组中长度较小的那个然后通过标记来记录是否发生过交换确保答案的点顺序的正确性。 每次从优先队列中取出堆顶元素这个堆顶就是当前未被加入到答案的所有点对中的最小值加入答案并将该点对所在序列的下一位如果有的话加入到优先队列。
代码
class Solution {boolean flag true;public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {int n nums1.length, m nums2.length;if(n m !(flag false))return kSmallestPairs(nums2, nums1, k);ListListInteger ans new ArrayList();PriorityQueueint[] q new PriorityQueue((a,b) - (nums1[a[0]] nums2[a[1]]) - (nums1[b[0]] nums2[b[1]]));// 如果nk的话那我们其实只需要建立nums1的前k个序对就够了for(int i0; iMath.min(n, k) ;i){q.add(new int[]{i,0});}while(ans.size() k !q.isEmpty()){int[] poll q.poll();int a poll[0], b poll[1];ans.add(new ArrayList(){{add(flag ? nums1[a] : nums2[b]);add(flag ? nums2[b] : nums1[a]);}});if(b1 m)q.add(new int[]{a, b1});}return ans;}
}
