Merge sorted arrays?-CodePudding

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);
}

CodePudding user response：

As per your code, there will be duplicates in the output. To remove duplicates you need to modify the condition to this in the first while:

while (i < a.length && j < b.length)  
   answer[k  ] = a[i] <= b[j] ? a[i  ] :  b[j  ];

This shall skip one of the duplicate from other array.

Also need to check if the output array already contains the same element in the previous index and skip that.

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

Similarly in other whiles too.

CodePudding user response：

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.

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);
        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]