Merge two arrays and remove duplicates in Java

Question

I am having trouble removing the duplicates from two arrays that have been merged into one. I have written the following code that merges the arrays, yet I'm not sure how to remove the duplicates from the final array. Assume the arrays are already sorted.

public static int[] merge(int[] list1, int[] list2) {
    int[] result = new int[list1.length + list2.length];

    int i = 0;
    int j = 0;

    for (int k = 0; k < (list1.length + list2.length); k++) {
        if (i >= list1.length) {
            result[k] = list2[j];
            j++;
        } 
        else if (j >= list2.length) {
            result[k] = list1[i];
            i++;
        } 
        else {
            if (list1[i] < list2[j]) {
                result[k] = list1[i];
                i++;
            } else {
                result[k] = list2[j];
                j++;
            }
        }
    }
    return result;
}

I don't know what the context of the problem is, or how critical the memory usage/speed of your program is, but you should start using collections. You could do all this in one or two lines. — MikaelF, Feb 05 '17 at 04:39

score 5 · Accepted Answer · edited May 23 '17 at 12:33

Ok, someone hated all the answers. Here's another attempt that combines two stackoverflow q's, combining arrays and removing dupes.

This one runs a good deal faster than my earlier attempt on two lists of a million ints.

public int[] mergeArrays2(int[] arr1, int[] arr2){
    int[] merged = new int[arr1.length + arr2.length];
    System.arraycopy(arr1, 0, merged, 0, arr1.length);
    System.arraycopy(arr2, 0, merged, arr1.length, arr2.length);

    Set<Integer> nodupes = new HashSet<Integer>();

    for(int i=0;i<merged.length;i++){
        nodupes.add(merged[i]);
    }

    int[] nodupesarray = new int[nodupes.size()];
    int i = 0;
    Iterator<Integer> it = nodupes.iterator();
    while(it.hasNext()){
        nodupesarray[i] = it.next();
        i++;
    }



    return nodupesarray;
}

console output:

INFO [main] (TestMergeArray.java:40) - creating two lists of a million ints
DEBUG [main] (TestMergeArray.java:41) - list 1 size : 1000000
DEBUG [main] (TestMergeArray.java:42) - list 2 size : 1000000
INFO [main] (TestMergeArray.java:56) - now merging
INFO [main] (TestMergeArray.java:59) - done, final list size is 864975

this answer does not take into account the fact that user is merging two sorted arrays and wants to maintain the sort. — Patrick Parker, Feb 05 '17 at 05:25

score 2 · Answer 2 · answered Nov 11 '19 at 16:06

this clearer lambda solution is slightly slower because of the (un)boxing
requires Java 8 or above

public static int[] mergedistinct( int[] array1, int[] array2 ) {
  Stream<Integer> s1 = IntStream.of( array1 ).boxed();
  Stream<Integer> s2 = IntStream.of( array2 ).boxed();
  return( Stream.concat( s1, s2 ).distinct().mapToInt( i -> i ).toArray() );
}

[1, 2, 3, 5, 4, 7, 8]

if you need the array sorted:

…
return( Stream.concat( s1, s2 ).distinct().sorted().mapToInt( i -> i ).toArray() );

score 1 · Answer 3 · edited May 07 '21 at 05:26

Here's a technique that iterates the arrays just once and does not use a hash to detect duplicates.

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class SortedMerge {
    public static int[] merge(int[] array1, int[] array2) {
        int[] a;
        int[] b;
        List<Integer> c = new ArrayList<Integer>();
        int i = 0;
        int j = 0;

        // b is longer than a
        if (array1.length > array2.length) {
            a = array2;
            b = array1;
        } else {
            a = array1;
            b = array2;
        }

        while (j < b.length) {
            int bb = b[j];

            if (i < a.length) {
                int aa = a[i];

                if (aa > bb) {
                    c.add(bb);
                    j++;
                } else {
                    c.add(aa);
                    i++;
                    if (aa == bb) {
                        j++;
                    }
                }
            } else {
                c.add(bb);
                j++;
            }
        }
        // java 8 List<Integer> to int[]
        return c.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) throws Exception {
        int[] array1 = new int[]{3, 5, 8, 11, 14};
        int[] array2 = new int[]{1, 2, 3, 4, 6, 8, 14, 15, 17};
        int[] c = merge(array1, array2);

        for (int i = 0; i < c.length; i++) {
            System.out.format("%d,", c[i]);
        }
        System.out.println();
        // output> 1,2,3,4,5,6,8,11,14,15,17,
    }
}

score 0 · Answer 4 · edited May 06 '21 at 15:54

0

Call your merge method and do the followings. I tested it. It works fine.

int[] result = merge(count, count1);

Set<Integer> set = new HashSet<Integer>();
try {
    for (int i = 0; i < result.length; i++) {
        set.add(result[i]);
    }
    System.out.println(set);
} catch (Exception e) { }

edited May 06 '21 at 15:54

Community

1
1

answered Feb 04 '17 at 20:48

Zenith

837
1
7
20

JoryAnderson · Answer 5 · 2017-02-05T04:41:52.157

0

Can you use ArrayLists? ArrayLists would make this very easy to do.

 //Consider n1 to be some global or instance variable.

 import java.util.ArrayList;
 public void Add(ArrayList<Integer> n2) {

     for(int i = 0; i < n2.size(); i++) {
         if(!n1.contains(i))
             n1.add(n2.get(i));
     }
}

edited Feb 05 '17 at 04:41

answered Feb 05 '17 at 04:33

JoryAnderson

103
7

score 0 · Answer 6 · edited May 07 '21 at 05:27

package com.string.merge;

import java.util.ArrayList;

public class MergeArrayAndRemoveDuplicate {
    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 1, 5, 3};
        int[] b = {4, 3, 1, 5, 7, 8, 4, 2};

        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 0; i < (a.length > b.length ? a.length : b.length); i++) {
            if (i < a.length) {
                int c = 0;
                while (c <= l.size()) {
                    if (l.contains(a[i]) == false) {
                        l.add(a[i]);
                    }
                    c++;
                }
            }
            if (i < b.length) {
                int c = 0;
                while (c <= l.size()) {
                    if (l.contains(b[i]) == false) {
                        l.add(b[i]);
                    }
                    c++;
                }
            }
        }
        System.out.println(l);
    }
}

o/p-[1, 4, 2, 3, 5, 7, 8]

score 0 · Answer 7 · edited May 06 '21 at 16:54

import java.util.ArrayList;
import java.util.List;
public class MergeListAndRemoveDuplicate {
    public static void main(String[] args) {
        int a[] = {1, 1, 2, 1, 3, 4, 1, 2, 5};
        int b[] = {1, 2, 3, 1, 3, 2, 4, 5, 6, 7};

        boolean flag = true;
        List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                if (a[i] == b[j]) {
                    flag = false;
                }
                if (i == j && !list.contains(b[j])) {
                    list.add(b[j]);
                }
            }
            if (flag == true) {
                list.add(a[i]);
            }
        }
        System.out.println(list);
    }
}

Merge two arrays and remove duplicates in Java

7 Answers7

Linked

Related