程序员面试金典10.01_合并排序的数组

—

题目

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:输入:

A = [1,2,3,0,0,0], m = 3

B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

说明:A.length == n + m

—

解题思路分析

1、合并后排序；时间复杂度O(nlog(n))，空间复杂度O(1)

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

2、双指针法；时间复杂度O(n)，空间复杂度O(1)

func merge(A []int, m int, B []int, n int) { for m > 0 && n > 0 { if A[m-1] < B[n-1] { A[m+n-1] = B[n-1] n-- } else { A[m+n-1] = A[m-1] m-- } } if m == 0 && n > 0 { for n > 0 { A[n-1] = B[n-1] n-- } }}

3、数组辅助；时间复杂度O(n)，空间复杂度O(n)

func merge(A []int, m int, B []int, n int) { temp := make([]int, m) copy(temp, A)
 if n == 0 { return } first, second := 0, 0 for i := 0; i < len(A); i++ { if second >= n { A[i] = temp[first] first++ continue } if first >= m { A[i] = B[second] second++ continue } if temp[first] < B[second] { A[i] = temp[first] first++ } else { A[i] = B[second] second++ } }}