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
31
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)
}