Note:
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.
Idea: Start from the end of A and B, copy the larger of A[i] and B[j] to the corresponding index (i+j+1) of A.
Time: O(n) Space: O(1)
Code:
public class Solution {
public void merge(int A[], int m, int B[], int n) {
int i=m-1;
int j=n-1;
while(i>=0||j>=0)
{
int v1=i<0?Integer.MIN_VALUE:A[i];
int v2=j<0?Integer.MIN_VALUE:B[j];
if(v1>=v2)
A[i+j+1]=A[i--];
else
A[i+j+1]=B[j--];
}
}
}
No comments:
Post a Comment