Removing duplicates using collections in Java when merging two sorted arrays

Question

I am trying to learn some Algorithms and I want to remove the duplicates using Set. I am merging two sorted arrays using my small algorithm which checks if the number from array A is small than B store in C, then later adds the remaining arrays

I have tried but keeps getting confused

    //arrays must be sorted
    int a [] = {1,3,4,5};
    int b [] = {5,6,8,9,10};

    System.out.println(Arrays.toString(combineArray(a,b,3,4)));

}

private static int[] combineArray(int[] A, int[] B, int m, int n) {

    // TODO Auto-generated method stub

    int i = 0;
    int j = 0;
    int k = 0;
    int c [] = new int[9];
    while(i <= m && j <= n) {

        if(A[i] < B[j]) {

            c[k++] = A[i++];

        }else {
            c[k++] = B[j++];
        }

    }

    for(; i <=m; i++) {
        c[k++] = A[i];
    }

    for(; j <=n ; j++) {
        c[k++] = B[j];
    }




    return c;
}

No error just wants some help with removing the duplicates.

"No error just wants some help." - in that case, what help do you need? — Eran, May 23 '19 at 11:13

ItFreak · Accepted Answer · 2019-05-23T19:03:33.337

You do not need to use an own algorithm, Java 8+ can do this nice and clean:

int[] array1 = {1, 2, 65, 4, 8, 5, 7, 18, 6, 0};
    int[] array2 = {0, 2, 11, 12, 5, 6, 8};
    int[] merged = IntStream.concat(IntStream.of(array1), IntStream.of(array2))
        .distinct()
        .sorted()
        .toArray();

Edit

It seems that calling distinct() after sorted() is faster.
See here:
Java Streams: How to do an efficient "distinct and sort"?

So it is probably better to do:

int[] array1 = {1, 2, 65, 4, 8, 5, 7, 18, 6, 0};
    int[] array2 = {0, 2, 11, 12, 5, 6, 8};
    int[] merged = IntStream.concat(IntStream.of(array1), IntStream.of(array2))
        .sorted()
        .distinct()
        .toArray();

To your posted algorithm:

I debugged your programm to the following state:

i=3, j=0 k=3.

The output of c is then: 1,3,4,0...

In this step, you did the follwing compare: A[3] < B[0] , which is 5<5 which is false, so the else enters. There, the 5 of B[] is added. In the next step, weve got i=3 (nothing changed because the first if was not entered!), j=1 and k=4, so we are checking: A[3] < B[1] which evaluates to true, because 5<6, so A[i++] will be added, that is A[4] which is 5. That is where the doubled five comes from. Now how to solve this?

I hope you are clear that the if-statements are your problem where you are checking for smaller-or-equal, which means in fact that it is "allowed" to enter a condition twice: one time when the first operand is smaller than the second one and the second time when both are equal. Since you have got this case in if-statements for both arrays, you will have duplicates. Only one if-condition is allowed to check for smaller-or-equal. So if you change your code:

private static int[] combineArray(int[] A, int[] B, int m, int n) {

int i = 0;
int j = 0;
int k = 0;
int c[] = new int[9];
while (i < m && j < n) {

    if (A[i] < B[j]) {

        c[k++] = A[i++];

    } else {
        c[k++] = B[j++];
    }

}


for (; i < m; i++) {
    c[k++] = A[i];
}

for (; j <= n; j++) {
    c[k++] = B[j];
}


return c;

}

It will not enter twice and won't add duplicated numbers twice. For your example, the output is:
[1, 3, 4, 5, 6, 8, 9, 10, 0]

Since duplicates are removed, there is one 0.

If the arrays to be merged are already sorted, your approach will be less efficient (O(nlogn) instead of O(n)). — Eran, May 23 '19 at 11:15
Hey, this is okay, but my biggest question is based on being able to write my own for learning purposes. I was wondering how I can remove the 5 per say in the final display. — Maria, May 23 '19 at 12:00

Removing duplicates using collections in Java when merging two sorted arrays

1 Answers1