Leetcode数据结构题目集的第二题🎉🎈
这次分别是“合并两个有序数组”和“两数之和”,由于两数之和之前已经做过了这里就不再赘述了。

合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。

示例 1:

1
2
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]

示例 2:

1
2
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]

解题思路&题解

已知m, n为nums1, nums2的元素数量且nums1的空间大小等于 m + n,也就是说通过切片 我们能拿到nums1实际需要的元素内容。
由于nums1的空间大小足够我们合并,因此可以直接将nums2的内容直接添加到nums1数组的m - 1后面,然后再对合并后的数组进行排序则得到了题解。
代码如下:

1
2
3
4
5

func merge(nums1 []int, m int, nums2 []int, n int) {
nums1 = append(nums1[:m], nums2...)
sort.Ints(nums1)
}

官方题解

官方的第一个解法其实就是我上面的解法,此外还有一个解法是我没有想出来的,看完后加上个人理解复现一下。

这里放一张leetcode官方的动图,直观的看到原理。

原理:利用两个point变量来模拟指针,数组看成一个队列 当其中一个队列遍历完后退出循环。代码中有详细的注释辅助理解。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func merge(nums1 []int, m int, nums2 []int, n int) {
// 存放结果
res := make([]int, 0, m+n)
// 两个数组的指针
point1, point2 := 0, 0

for {
// 数组一循环完, 将数组二剩余元素添加到结果里面
if point1 == m {
res = append(res, nums2[point2:]...)
break
}
// 与上面同理
if point2 == n {
res = append(res, nums1[point1:]...)
break
}
// 比较两个队列头的值,将小的放入结果数组中
if nums1[point1] < nums2[point2] {
res = append(res, nums1[point1])
point1++
} else {
res = append(res, nums2[point2])
point2++
}
}
// 不太清楚leetcode的判题程序,这里无法改变nums1的引用,因此使用copy复制。
// nums1 = res
copy(nums1, res)
}