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.
思路：将两个给定排序好的数组A和B，将B合并到A中去，意思应该就是不能借用中间变量数组。如果从前面一个一个比较，那么A中的数组就要往后移，时间复杂度是O(m^2).故我们反向考虑，从后面开始往前判断。合并和的数组长度是m+n,那么我们就从A和B最后一个元素往前判断，将大的那个数存入A[m+n-1]，依次往前判断。
class Solution { public: void merge(int A[], int m, int B[], int n) { int index=m+n-1; int i=m-1; int j=n-1; while(i>=0 && j>=0 && index>=0) { if(A[i]>B[j]) { A[index]=A[i]; i--; index--; } else { A[index]=B[j]; j--; index--; } } while(i>=0)//A还有剩下元素没有判断，B已经没有了，则A直接赋值。 { A[index]=A[i]; index--; i--; } while(j>=0)//B还有剩下元素没有判断，A已经没有了，则B剩下元素直接赋值到A中。 { A[index]=B[j]; index--; j--; } } };
Merge Sorted Array,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3601492.html