Description
Given two sorted integer arrays A and B, merge B into A as one sorted array.
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 n respectively.
Example
Example 1:
Input：[1, 2, 3] 3 [4,5] 2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]
Example 2:
Input：[1,2,5] 3 [3,4] 2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]
Solution
思路类似插入排序
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
// put B into the end of A
for (int i = m;i< m+n ;i++ ){
A[i] = B[i-m];
}
for (int i = m;i< m+n ;i++ ){
int j = i;
while(j>0){
if(A[j] < A[j-1]){
int tmp = A[j];
A[j] = A[j-1];
A[j-1] = tmp;
j--;
}else{
break;
}
}
}
}