给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组 数据范围： 0 ≤ � , � ≤ 100 0≤n,m≤100， ∣ � � ∣ < = 100 ∣A i ​ ∣<=100， ∣ � � ∣ < = 100 ∣B i ​ ∣<=100 注意： 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印 3. A 数组在[0,m-1]的范围也是有序的

解法一：

从 A 数组和 B 数组的末尾开始比较，将较大的数存放在 A 数组的末尾。需要用三个指针：p1 指向 A 数组的末尾，p2 指向 B 数组的末尾，p3 指向合并后的数组的末尾。每次比较后将较大的数存放在 p3 所指向的位置，并将指针向前移动一位。当 p1 或 p2 到达数组的开头时，将另一个数组中尚未处理的元素全部存放在 A 数组中。

时间复杂度：O(m+n)

空间复杂度：O(1)

class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int p1 = m - 1, p2 = n - 1, p3 = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (A[p1] > B[p2]) {
A[p3--] = A[p1--];
} else {
A[p3--] = B[p2--];
}
}
while (p2 >= 0) {
A[p3--] = B[p2--];
}
}
};

解法二：

先将 B 数组中的元素复制到 A 数组的后面，再使用归并排序对整个数组 A 进行排序。

时间复杂度：O((m+n)log(m+n))

空间复杂度：O(m+n)

class Solution {
public:
void merge(int A[], int m, int B[], int n) {
for (int i = 0; i < n; i++) {
A[m + i] = B[i];
}
mergeSort(A, 0, m + n - 1);
}

void mergeSort(int A[], int left, int right) {
if (left >= right) return;
int mid = (left + right) >> 1;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}

void merge(int A[], int left, int mid, int right) {
int temp[right - left + 1];
int p1 = left, p2 = mid + 1, p3 = 0;
while (p1 <= mid && p2 <= right) {
if (A[p1] <= A[p2]) {
temp[p3++] = A[p1++];
} else {
temp[p3++] = A[p2++];
}
}
while (p1 <= mid) {
temp[p3++] = A[p1++];
}
while (p2 <= right) {
temp[p3++] = A[p2++];
}
for (int i = 0; i < p3; i++) {
A[left + i] = temp[i];
}
}
};