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 tom+n) to hold additional elements from B. The number of elements initialized in A and B aremandnrespectively.
这里比较好的一个条件就是数组A是已经给定了存储空间的数组，这样的一个merge函数在归并算法中经常会用到
第一种应该是最愚蠢的做法，重新开辟了一个m+n的内存空间
class Solution {public:void merge(int A[], int m, int B[], int n) {int *C = new int[m+n];int i = 0;int j = 0;int k = 0;while(i < m && j < n){if(A[i] <= B[j]){C[k++] = A[i++];}if(A[i] > B[j]){C[k++] = B[j++];}}while(i < m){C[k++] = A[i++];}while(j < n){C[k++] = B[j++];}for(i = 0; i < k;i++){A[i] = C[i];}delete []C;}};但是题目中已经提到A数组是有序的，，而且长度很大，应该合理利用这个信息：class Solution {public:void merge(int A[], int m, int B[], int n) {int i = m-1;int j = n-1;int k= m+n-1;while(i >= 0 && j >= 0){if(A[i] >= B[j]){A[k–] = A[i–];}if(A[i] < B[j]){A[k–] = B[j–];}}while(j >= 0){A[k–] = B[j–];}}};
唯有斯人面上簌簌流下的，是点点无声无行的热泪。
