Last active
November 1, 2016 23:19
-
-
Save nashid/b4375cb458f8d8a595d5ba614bfef729 to your computer and use it in GitHub Desktop.
Given two sorted arrays merge them into a new array and keep the merged array sorted
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package kata; | |
import java.util.Arrays; | |
/* | |
* input1 = { 3, 8, 17, 99} | |
* input2 = { 5, 17, 88} | |
* output = { 3, 5, 8, 17, 88, 99} | |
*/ | |
public class MergeSortedArray { | |
private static void print(int input[]) { | |
if (null == input || input.length == 0) { | |
System.out.println("null Or Empry"); | |
return; | |
} | |
for (int i = 0; i < input.length; i++) { | |
System.out.print(input[i] + " "); | |
} | |
System.out.println(); | |
} | |
public static int[] mergeArrayWithNewArray(int input1[], int input2[]) { | |
int output[] = new int[input1.length + input2.length]; | |
int p1 = 0, p2 = 0, out = 0; | |
while (p1 < input1.length && p2 < input2.length) { | |
if (input1[p1] < input2[p2]) { | |
output[out++] = input1[p1++]; | |
} | |
else if (input1[p1] == input2[p2]) { | |
output[out++] = input1[p1++]; | |
output[out++] = input2[p2++]; | |
} | |
else { | |
// input1[p1] > input2[p2] | |
output[out++] = input2[p2++]; | |
} | |
} | |
// p1 contains greater value | |
while (p1 < input1.length) { | |
output[out++] = input1[p1++]; | |
} | |
// on the other hand p2 contains greater numbers | |
while (p2 < input2.length) { | |
output[out++] = input2[p2++]; | |
} | |
return output; | |
} | |
/* | |
* merge two sorted array array1 and array2 into the array1 (array1 has enough space) | |
*/ | |
public static int[] mergeArray(int input1[], int input2[], int array1Length) { | |
int p1 = array1Length-1, p2 = input2.length-1; | |
int out = array1Length + input2.length -1; | |
while( index1 > 0 && index2>=0 ) { | |
if(input1[p1] < input2[p2]) { | |
input1[out--] = input2[p2--]; | |
} | |
else { | |
input1[out--] = input1[p1--]; | |
} | |
} | |
while(p2>=0) { | |
input1[out--] = input2[p2--]; | |
} | |
return input1; | |
} | |
public static void main(String args[]) { | |
System.out.println(Arrays.toString(mergeArray(new int[]{}, new int[]{}))); | |
System.out.println(Arrays.toString(mergeArray(new int[]{3, 8, 17, 99}, | |
new int[]{5, 17, 88}))); | |
System.out.println(Arrays.toString(mergeArray(new int[]{}, | |
new int[]{5, 17, 88}))); | |
System.out.println(Arrays.toString(mergeArray(new int[]{3, 8, 17}, | |
new int[]{}))); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment