如果另外开辟一个数组C，A,B从头开始比较，谁小，谁最先放到中，题上说最后都放到A中，那么就扫描C，复制数据就行了，时间复杂度O（m+n）,空间复杂度O(m+n)
当然还有比这个好的办法，空间复杂度O(1).
1 void merge(int A[], int m, int B[], int n) { 2 int C[m+n]; 3 int i=0,j=0,k=0; 4 while(i<m&&j<n){ 5 if(A[i]<=B[j]){ 6 C[k]=A[i]; 7 i++; 8 k++; 9 } 10 else{ 11 C[k]=B[j]; 12 j++; 13 k++; 14 } 15 } 16 if(i<m){ 17 C[k]=A[i]; 18 k++; 19 i++; 20 } 21 else if(j<n){ 22 C[k]=B[j]; 23 k++; 24 j++; 25 } 26 for(i=0;i<k;++i) 27 A[i]=C[i]; 28 }
Status: Wrong Answer
| Input: | [1,2,3], [2,5,6] |
| Output: | [1,2,2,3,5,513] |
| Expected: | [1,2,2,3,5,6] |
呃，在codeblocks中调试时才发现16-25写错的。
不应该是if,应该是while哇······（其实我犯这错误不是一次两次啦）
从后向前比，空间复杂度O（1）
1 void merge(int A[], int m, int B[], int n) { 2 int i,j,k; 3 i=m-1; 4 j=n-1; 5 k=m+n-1; 6 while(i>=0&&j>=0){ 7 if(A[i]<B[j]){ 8 A[k]=B[j]; 9 j--; 10 } 11 else{ 12 A[k]=A[i]; 13 i--; 14 } 15 k--; 16 } 17 while(i>=0){ 18 A[k]=A[i]; 19 k--; 20 i--; 21 } 22 while(j>=0){ 23 A[k]=B[j]; 24 k--; 25 j--; 26 } 27 }
Merge Sorted Array,布布扣,bubuko.com
原文：http://www.cnblogs.com/crane-practice/p/3617969.html