Issue
How can I merge and print two sorted arrays without any duplicates? I tried but not able to land on any efficient solution.
public static void mergeSortedArrays(int a[], int b[]) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
while (i < a.length)
answer[k++] = a[i++];
while (j < b.length)
answer[k++] = b[j++];
System.out.print(answer);
}
Solution
You stated that both arrays are sorted and I assume that the merged array also needs to be sorted.
Here is the code. Explanations follow it.
(NOTE: Code edited due to OP comment.)
import java.util.Arrays;
public class Test {
private static int[] mergeSortedArrays(int[] a, int[] b) {
int[] temp = new int[a.length + b.length];
int i = 0;
int j = 0;
int k = 0;
while (i < a.length) {
if (j < b.length) {
if (a[i] < b[j]) {
temp[k++] = a[i++];
}
else if (a[i] == b[j]) {
temp[k++] = a[i++];
j++;
}
else {
temp[k++] = b[j++];
}
}
else {
temp[k++] = a[i++];
}
}
if (j < b.length) {
for (; j < b.length; j++) {
temp[k++] = b[j];
}
}
int[] answer = new int[k];
System.arraycopy(temp, 0, answer, 0, k);
/* Added */
System.out.print(answer[0]);
for (i = 1; i < k; i++) {
System.out.print(", " + answer[i]);
}
System.out.println();
/**/
return answer;
}
public static void main(String[] args) {
int[] a = {-19, -5, -4, 3, 7, 8, 11, 21};
int[] b = {-7, -5, -4, 0, 3, 6, 11, 13, 20};
System.out.println(Arrays.toString(mergeSortedArrays(a, b)));
}
}
We compare an element from the first array with an element from the second array. The smaller of the two is copied to the result array. Then we increment the index of the array whose element was copied to the result array. If the elements are equal, we [arbitrarily] copy the element from the first array and increment the index on both arrays. This prevents the result array from containing duplicates.
If the arrays do not have equal number of elements, then when we have exhausted one array, we simply copy all the remaining elements from the longer array to the result array.
Hence the result array contains all the elements from the two arrays, without duplicates, sorted.
Here is the output when I run the above code.
-19, -7, -5, -4, 0, 3, 6, 7, 8, 11, 13, 20, 21
[-19, -7, -5, -4, 0, 3, 6, 7, 8, 11, 13, 20, 21]
Answered By - Abra
Answer Checked By - Robin (JavaFixing Admin)