LeetCode88-合并两个有序数组

题目描述

给定两个非递减顺序排列的数组 nums1 和 nums2 以及两个数组中元素个数 m 和 n，要求将 nums2 合并到 nums1 中并保持非递减顺序，其中 nums1 数组的长度是 m + n。

示例：

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

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

思路

1. 定义两个指针 p1 和 p2，分别指向 nums1 和 nums2，遍历 nums2，比较 nums[p1] 和 nums[p2] 的大小，当 nums[p1] 大于 nums[p2] 的时候，将 nums[p2] 的值插入到 nums[p1] 前面，直到 p2 = n - 1 结束。不过这种方式每次插入 nums1 都需要移动后半部分的元素，效率比较低；还需要考虑 nums1 先遍历结束的情况。
2. 同 1 类似，定义两个指针 p1 和 p2 分别指向 nums1 的最后一个元素 和 num2 的最后一个元素，利用数组非递减的特性，比较 nums[p1] 和 nums[p2]，将较大值直接放到 nums1 的最后一个空位，直到 nums2 中的元素都被处理完。另外需要考虑 nums1 中的所有元素都大于 nums2 中的元素，p1 会变为负数，此时只需要将 nums2 的元素直接放到 nums1 对应的位置即可。

代码实现

go 代码实现如下：

func merge(nums1 []int, m int, nums2 []int, n int) {
	if m == 0 {
		for i := range n {
			nums1[i] = nums2[i]
		}
		return
	}
	if n == 0 {
		return
	}

	p1 := m - 1
	p2 := n - 1
	tempIndex := m + n - 1

	for p2 >= 0 {
		if p1 >= 0 && p2 >= 0 && nums1[p1] >= nums2[p2] {
			nums1[tempIndex] = nums1[p1]
			nums1[p1] = 0
			p1--
		} else {
			nums1[tempIndex] = nums2[p2]
			p2--
		}
		tempIndex--
	}
}