做网站需要展示工厂么,中国万网注册网站,养殖业网站模板,邢台建网站哪里有文章目录题目描述题目链接题目难度——简单方法一#xff1a;常规双指针遍历代码/Python方法二#xff1a;字典\哈希表代码/Python总结题目描述
给你两个 二维 整数数组 nums1 和 nums2.
nums1[i] [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。nums2[i] [idi, …
文章目录题目描述题目链接题目难度——简单方法一常规双指针遍历代码/Python方法二字典\哈希表代码/Python总结题目描述
给你两个 二维 整数数组 nums1 和 nums2.
nums1[i] [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。nums2[i] [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。
每个数组都包含 互不相同 的 id 并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组并符合下述条件
只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。每个 id 在结果数组中 只能出现一次 并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id 则认为其对应的值等于 0 。
返回结果数组。返回的数组需要按 id 以递增顺序排列。 示例 1
输入nums1 [[1,2],[2,3],[4,5]], nums2 [[1,4],[3,2],[4,1]] 输出[[1,6],[2,3],[3,2],[4,6]] 解释结果数组中包含以下元素
id 1 对应的值等于 2 4 6 。id 2 对应的值等于 3 。id 3 对应的值等于 2 。id 4 对应的值等于5 1 6 。
示例 2
输入nums1 [[2,4],[3,6],[5,5]], nums2 [[1,3],[4,3]] 输出[[1,3],[2,4],[3,6],[4,3],[5,5]] 解释不存在共同 id 在结果数组中只需要包含每个 id 和其对应的值。 提示
1 nums1.length, nums2.length 200nums1[i].length nums2[j].length 21 idi, vali 1000数组中的 id 互不相同数据均按 id 以严格递增顺序排列
题目链接
题目难度——简单
方法一常规双指针遍历 题目给的数据已经是有序的那么我们可以用两个指针分别遍历这两个数组同时保证结果有序加入结果数组中只不过这样略显麻烦。
代码/Python
class Solution:def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) - List[List[int]]:p1, p2 0, 0n1 len(nums1)n2 len(nums2)res []while p1 n1 and p2 n2:if nums1[p1][0] nums2[p2][0]:res.append([nums1[p1][0], nums1[p1][1] nums2[p2][1]])p1 1p2 1elif nums1[p1][0] nums2[p2][0]:res.append(nums1[p1])p1 1else:res.append(nums2[p2])p2 1while p1 n1:res.append(nums1[p1])p1 1while p2 n2:res.append(nums2[p2])p2 1sorted(res)return res 方法二字典\哈希表 题目说的请款完全符合一个字典的情况所以我们可以用一个字典来存储两个数组中每个数及其对应值。
代码/Python
class Solution:def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) - List[List[int]]:table defaultdict(int)for i, val in nums1 nums2:table[i] valreturn sorted([[k, v] for k, v in table.items()])总结 因为有排序所以方法一和二的时间复杂度都是O(logN)方法一的空间复杂度O(1) 方法二空间O(N)。
