LeetCode Problem
88. Merge Sorted Array
Link to LeetCode
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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
Analysis
The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case.
The takeaway message from this problem is that the loop condition.
This kind of condition is also used for merging two sorted linked list.
public class Solution {
public void merge(int A[], int m, int B[], int n) {
while(m > 0 && n > 0){
if(A[m-1] > B[n-1]){
A[m+n-1] = A[m-1];
m--;
}else{
A[m+n-1] = B[n-1];
n--;
}
}
while(n > 0){
A[m+n-1] = B[n-1];
n--;
}
}
}
//The loop condition also can use m+n like the following.
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 (k >= 0) {
if (j < 0 || (i >= 0 && A[i] > B[j]))
A[k--] = A[i--];
else
A[k--] = B[j--];
}
}