Merge two unsorted integer arrays without using Set in Java

Question

Given two integer arrays, create a third array containing non-duplicate values from both arrays. Can't use Set implementations in Java, here is how I solved it and I was hoping to find a solution with better runtime complexity.

My implementation:

public static void removeDuplicates(int[] arr1, int[] arr2){
        int[] arr = new int[arr1.length + arr2.length];
        int index=0,i,j;

        for (i=0;i<arr1.length;i++){
            if(!contains(arr, arr1[i])){
                arr[index++]=arr1[i];
            }
        }

        for (j = 0; j < arr2.length; j++) {
            if (!contains(arr, arr2[j])) {
                arr[index++] = arr2[j];
            }
        }

        for (int a: arr)
            System.out.println(a);
    }

    private static boolean contains(int[] arr, int i) {
        for (int a: arr){
            if(a==i) return true;
        }
        return false;
    }

Well you don't have any question, but you can get better complexity than O(n*m) , make your own mergeSort — nachokk
– nachokk, Commented Feb 24, 2014 at 18:11
Are you all blind? His question is how to get better complexity. — trutheality
– trutheality, Commented Feb 24, 2014 at 18:12
@trutheality and that's belong to stackoverflow or belongs to another stackexchange site? — nachokk
– nachokk, Commented Feb 24, 2014 at 18:12

Gorkk · Accepted Answer · 2014-02-24 18:25:30Z

This is indeed of quadratic complexity due to the contains calls. You could improve your algorithm by first sorting both arrays, and then procede to a merging akin to what you would do in the merge step of a mergesort, but adding the entries only if the previous entry is not the same.

You'd have to keep a reference to the last index with data after the merge, so you can at the end resize your array to a smaller one and avoid empty cells.

update Some precisions for the merge part: you would start at the beginning of both sorted arrays, and take the smaller of both items at this index, then increment the index for the array you took one. Considering your arrays a and b, target being your target array, i the index cursor for a, j for b and k for target:

you start with i = j = k = 0
you take v = min(a[i], b[j]) and increment the relevant index (i if you took from a, j if you took from b)
if target[k-1] == v (when k > 0 of course), you just increment k (i.e. ignore the value as it's already in the array)
else you do target[k++] = v (i.e. put v at index k in target and then increment k)
at the end you will have k equals to the real size of your target array so you can trim down the array to an array of size k <= a.length + b.length

Of course during the process, once you have exhausted one of the two arrays, you just take from the other and compare with the last value in target.

Collectives™ on Stack Overflow

Merge two unsorted integer arrays without using Set in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related