Given two sorted integer arrays A and B, merge B into A as one sorted array.
Example
A =
[1, 2, 3, empty, empty]
, B = [4, 5]
After merge, A will be filled as
[1, 2, 3, 4, 5]
Note
Analysis: We can just take advantage of the extra space of A to accommodate B.
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 and nrespectively.
class Solution { public: /** * @param A: sorted integer array A which has m elements, * but size of A is m+n * @param B: sorted integer array B which has n elements * @return: void */ void reverse(int A[], int start, int end) { while(start < end) { int tmp = A[start]; A[start] = A[end]; A[end] = tmp; start++; end --; } } void mergeSortedArray(int A[], int m, int B[], int n) { // write your code here if(0 == n) return ; int index = m; int i = 0, j = 0; while(j<n) { int toFit = index++ % (m+n); if(i<m && A[i] < B[j]) A[toFit] = A[i++]; else A[toFit] = B[j++]; } reverse(A, m,m+n-1); reverse(A, 0, m-1); reverse(A, 0,m+n-1); } };