合并两个有序的数组

1. 题目描述

给出两个有序的整数数组 和 ，请将数组 合并到数组 中，变成一个有序的数组 注意： 可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为 和

2. 思路

1. 思路一
   • 归并排序 归并排序.md
     • 从前往后
     • 从后往前

3. 实现

3.1. 从前往后

//时间：O(N)
//空间：O(N)
func merge(A []int, m int, B []int, n int) {
	res := make([]int, 0)

	i := 0
	j := 0
	for i < m && j < n {
		if A[i] < B[j] {
			res = append(res, A[i])
			i++
		} else {
			res = append(res, B[j])
			j++
		}
	}

	for i < m {
		res = append(res, A[i])
		i++
	}

	for j < n {
		res = append(res, B[j])
		j++
	}

	for i := 0; i < len(res); i++ {
		A[i] = res[i]
	}
}

3.2. 从后往前

//时间：O(N)
//空间：O(1)
func merge2(A []int, m int, B []int, n int) {
	i, j, k := m-1, n-1, m+n-1
	for i >= 0 && j >= 0 {
		if A[i] > B[j] {
			A[k] = A[i]
			i--
		} else {
			A[k] = B[j]
			j--
		}
		k--
	}
	for i >= 0 {
		A[k] = A[i]
		i--
		k--
	}
	for j >= 0 {
		A[k] = B[j]
		j--
		k--
	}
}

4. 参考

• 合并两个有序的数组_牛客题霸_牛客网