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 mand n respectively.
思路:从我们可以从A和B的末端开始归并,技巧是,一直找剩下的最大元素,放到A的后部。时间复杂度是O(m+n)。
void merge(int A[], int m, int B[], int n) { int k=m+n-1; // the end of the resulting array int i = m-1; // the end of A int j = n-1; // the end of B while(1) { while(i>=0 && j>=0 && A[i]>=B[j]) { A[k] = A[i]; k--; i--; } while(i>=0 && j>=0 && A[i]<=B[j]) { A[k] = B[j]; k--; j--; } if(i<0 || j<0) break; } if(i<0) while(j>=0) { A[k] = B[j]; k--; j--; } if(j<0) while(i>=0) { A[k] = A[i]; k--; i--; } }