/*
* Question:
Given two sorted arrays A1 and A2, of lengths L1 and L2 , L1 < L2 and the last L1
slots in A2 are vacant, get me all the numbers in A2, sorted in the most efficient
manner without using extra space.
* Solution:
* (Same question can be asked for merging more than 2 arrays
* follow the same pattern by merging 1 array with main array at a time)
*
* Run a for loop from end of A2 and compare A1 and A2 from their ends.
*
* Runtime: O(n);
* Space time: O(1);
*/
public class MergeTwoSortedArrays {
private int[] A1;
private int[] A2;
public MergeTwoSortedArrays() {
A1 = new int[4];
A2 = new int[10];
A1[0]= 2;
A1[1]= 4;
A1[2]= 7;
A1[3]= 9;
A2[0]= 1;
A2[1]= 3;
A2[2]= 5;
A2[3]= 6;
A2[4]= 8;
A2[5]= 10;
}
public void mergeTwoArrays(){
int l2 = 5;
int l1 = 3;
for(int i = A2.length-1; i>=0; i--) {
if(l1 >=0) {
if(A2[l2] > A1[l1]) {
A2[i] = A2[l2];
l2--;
}
else {
A2[i] = A1[l1];
l1--;
}
}
else {
break;
}
}
}
public void display() {
for(int i=0; i
}
}
public static void main(String args[]) {
MergeTwoSortedArrays obj = new MergeTwoSortedArrays();
obj.mergeTwoArrays();
obj.display();
}
}
No comments:
Post a Comment