题目链接：Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
这道题的要求是将有序数组B合并到有序数组A中，假设A有足够空间容纳B中所有元素。
归并排序中合并的步骤，不过由于是要合并到A中，也就是不申请额外空间，因此，为了减少移动A重元素的次数，考虑从后往前逐步合并：从后往前遍历A和B数组，每次把大的数字从A中m+n位置逐步往前放。
时间复杂度：O(m+n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
void merge(int A[], int m, int B[], int n)
{
int i = m - 1, j = n - 1, k = m + n - 1;
while(j >= 0)
{
if(i >= 0 && A[i] > B[j])
A[k --] = A[i --];
else
A[k --] = B[j --];
}
}
};