手写代码:合并有序数组
参考回答:
class Solution { public: void merge(int A[], int m, int B[], int n) { int i , j , k ; for( i = m - 1, j = n - 1, k = n + m -1; k >= 0; --k) { if( i >= 0 &&(j < 0 || A[i] >= B[j]) ) A[k] = A[i--]; else A[k] = B[j--]; } } };
解法二:由于合并后A数组的大小必定是m+n,所以从最后面开始往前赋值,先比较A和B中最后一个元素的大小,把较大的那个插入到m+n-1的位置上,再依次向前推。如果A中所有的元素都比B小,那么前m个还是A原来的内容,没有改变。如果A中的数组比B大的,当A循环完了,B中还有元素没加入A,直接用个循环把B中所有的元素覆盖到A剩下的位置。
class Solution { public: void merge(int A[], int m, int B[], int n) { int count = m + n - 1; --m; --n; while (m >= 0 && n >= 0) A[count--] = A[m] > B[n] ? A[m--] : B[n--]; while (n >= 0) A[count--] = B[n--]; } };