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.
考虑从后往前比较，这样就不会产生需要数据后移的问题了。时间复杂度O(n+m)
代码如下：
void merge(int A[], int m, int B[], int n) { int index, aindex,bindex; index = m+n-1; aindex = m-1; bindex = n-1; while(aindex >= 0 && bindex >= 0){ if(A[aindex] > B[bindex]){ A[index--] = A[aindex--]; }else{ A[index--] = B[bindex--]; } } while(bindex >= 0) A[index--] = B[bindex--]; }
class Solution { public: void merge(int A[], int m, int B[], int n) { int index = m + n - 1; int aIndex = m - 1; int bIndex = n - 1; while(0 <= aIndex && 0 <= bIndex) { if (B[bIndex] > A[aIndex]) { A[index--] = B[bIndex--]; } else { A[index--] = A[aIndex--]; } } while(0 <= bIndex) { A[index--] = B[bIndex--]; } } };
原文：http://www.cnblogs.com/zhhc/p/4351411.html