Skip to main content

Merge two sorted Lists or Arrays

Code to merge two array lists:

public static ArrayList<Integer> mergeLists(ArrayList<Integer> l1, ArrayList<Integer> l2){
ArrayList<Integer> l3 = new ArrayList<Integer>();

int i = 0;
int j = 0;
while(i < (l1.size()) && j < (l2.size())){
if(l1.get(i) < l2.get(j)){
l3.add(l1.get(i));
i++;
}else {
l3.add(l2.get(j));
j++;
}
}
if(i < l1.size()){
while(i < l1.size()){
l3.add(l1.get(i));
i++;
}
}else if(j < l2.size()){
while(j < l2.size()){
l3.add(l2.get(j));
j++;
}
}

return l3;
}

Code to merge two arrays:

public static int[] mergeArrays(int[] a, int[] b){

if((a == null || a.length == 0) && (b == null || b.length == 0))
return new int[0];

if((a == null || a.length == 0))
return b;

if(b == null || b.length == 0)
return a;

int[] c = new int[a.length + b.length];

int i,j,k;
i = j = k = 0;

while(i < a.length && j < b.length){
if(a[i] <=  b[j]){
c[k++] = a[i++];
}else
{
c[k++] = b[j++];
}
}

while(i < a.length){
c[k++] = a[i++];
}

while(j < b.length){
c[k++] = b[j++];
}

return c;
}

Complexity:
If length of the first array a and length of the second array is b, then complexity of this algorithm is O(a+b).

Comments

Post a Comment

Popular posts from this blog

Find second largest element in an array

Find second largest element in an unsorted array.               We can reach the solution in three ways.  Solution 1 Sort the array and return last but one element. We could use already existing sorting methods in JDK Arrays class and sort the array. public static int findSecondLargestV1( int [] array ){ if ( array . length == 0 || array . length < 2){ return -1; } Arrays.sort( array ); return array [ array . length - 2]; } Complexity: Since this solution depends on sorting, the complexity is equal to complexity of sorting algorithm, ie., O(n log n) Solution 2 public static int findSecondLargestV2( int [] array ){ if ( array . length == 0 || array . length < 2){ return -1; } int max = -1; for ( int i = 0; i < array . length ; i ++){ if ( array [ i ] > max ){ max = array [ i ]; } } int secondMax = -1; for (
1 comment
Read more

Binary search (recursive and non-recursive)

Recursive solution: public static int binarySearch( int [] array , int startIndex , int endIndex , int value ){ int midIndex = ( startIndex + endIndex )/2; if ( array [ midIndex ] == value ){ return value ; } if ( startIndex > endIndex ){ return -1; } if ( value < array [ midIndex ]){ int sI = startIndex ; int eI = midIndex - 1; return binarySearch( array , sI , eI , value ); } else { int sI = midIndex + 1; int eI = endIndex ; return binarySearch( array , sI , eI , value ); } } Non-Recursive solution: public static int binarySearchNoRecursion( int [] array ,  int value ){ int startIndex = 0; int endIndex = array . length - 1; while ( startIndex <= endIndex ){ int midIndex = ( startIndex + endIndex )/2; if ( array [ midIndex ] == value ){ return value ; } if ( value < ar
Post a Comment
Read more