Best implementation to remove duplicates JAVA array

Question

Found this solution to make this method:

int[] withoutDuplicates(int[] a){
int n = a.length;
   if (n < 2) {
        return a; 
    }
    for (int i = 0; i < n-1; i++) { 
         for (int j = i+1; j < n; j++) {
               if (a[j] == a[i]) {
                 --n;
                 System.arraycopy(a, j+1, a, j, n-j);
                --j; 
             }//end if
        } //end for
     }//end for

     int[] aa = new int[n]; 
     System.arraycopy(a, 0, aa, 0, n); 
     return aa;

}//end method

I do not understand why it is using an array of length n. Shouldn't it be of size n minus the number of duplicates erased? Is this the most optimal way of implementing the method? or is there any java resource I could use?

It _is_ n minus the number of duplicates. `--n` – takendarkk May 14 '14 at 15:54 — takendarkk, May 14 '14 at 15:54

jgitter · Accepted Answer · 2014-05-14T16:13:02.787

4

I am, by nature, lazy. I would do this:

-- EDIT --

private int[] withoutDuplicates(int[] a){
    Set<Integer> set = new LinkedHashSet<Integer>();
    for (int x : a) {
        set.add(x);
    }
    int[] newArray = new int[set.size()];
    int ii = 0;
    for (Integer x : set) {
        newArray[ii++] = x;
    }
    return newArray;
}

edited May 14 '14 at 16:13

answered May 14 '14 at 15:54

jgitter

3,396
1
19
26

It changes the order of it. That could be a unwished side effect of a duplicate erase method i think ;) – pL4Gu33 May 14 '14 at 15:58
3

`set.toArray(new int[]{})` doesn't compile ... If the method signature used Integer[] it would. – bdkosher May 14 '14 at 16:02
I assumed it would perform the auto-unboxing... I'll update shortly. – jgitter May 14 '14 at 16:04
Thanks, good observation – developerto_jrm May 14 '14 at 16:05
Here's a fixed, compilable implementation. It has the added benefit of preserving the order. Thanks @pL4Gu33 for the catch. – jgitter May 14 '14 at 16:13
That code looks really good. Thanks for the help – developerto_jrm May 14 '14 at 16:20

score 0 · Answer 2 · answered May 14 '14 at 19:17

Here is an algorithm for removing duplicates and maintaining the relative order. Time: O(n) Space: O(n)

public static void dupCheck(int [] a){
        int j=0;
        HashMap<Integer,Boolean> map = new HashMap<Integer,Boolean>();
        int [] b = new int [a.length];
        for(int i=0;i<a.length;i++){
            if(!map.containsKey(a[i])){
                map.put(a[i],true);
                b[j++]=a[i];
            }
        }
        for(int i=0;i<j;i++)
            System.out.print(b[i]+" ");
    }

Best implementation to remove duplicates JAVA array

2 Answers2