[LeetCode] 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 andn respectively.

思路：

直观思路显然是双指针i, j同时扫描A, B，选min(A[i], B[j])作为下一个元素插入。但是只能利用A后面的空间来插入，这样就很不方便了。

反向思路，merge后的数组一共有m+n个数。i, j从A, B尾部扫描，选max(A[i], B[j])插入从m+n起的尾部。这样也可以防止插入到A原来数字的范围内时，overwrite掉A原来的数。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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