给定两个排序后的数组 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]

第一种方法：

直接把B数组放在A数组的缓冲空间，然后再使用sort排序

class Solution {
public:void merge(vector<int>& A, int m, vector<int>& B, int n) {for(int i =m;i<m+n;i++){A[i] = B[i-m];}sort(A.begin(),A.end());}
};

第二种方法：

使用两个指针，一个过渡数组。
方法1没有利用数组 A 与 B 已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到过渡数组中，最后放回A数组中。

class Solution {
public:void merge(vector<int>& A, int m, vector<int>& B, int n) {int pa = 0, pb = 0;int sorted[m + n];int cur;while (pa < m || pb < n) {if (pa == m)cur = B[pb++];else if (pb == n)cur = A[pa++];else if (A[pa] < B[pb])cur = A[pa++];elsecur = B[pb++];sorted[pa + pb - 1] = cur;}for (int i = 0; i != m + n; ++i)A[i] = sorted[i];}
};作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sorted-merge-lcci/solution/mian-shi-ti-1001-he-bing-pai-xu-de-shu-zu-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。