Removing duplicate values from an array

Question

Here is my code for removing duplicated values from an array. I think I tested it with the most possible cases. Any suggestions or bugs?

class duplicate {

    public static int[] removeDuplicates(int[] arr) { 
        int end = arr.length;

        for (int i = 0; i < end; i++) {
            for (int j = i + 1; j < end; j++) {
                if (arr[i] == arr[j]) {                  
                    int shiftLeft = j;

                    for(int k = j + 1; k < end; k++, shiftLeft++) {
                        arr[shiftLeft] = arr[k];
                    }

                    end--;
                    j--;
                }
            }
        }

        int[] whitelist = new int[end];

        for (int i = 0; i < end; i++) {
            whitelist[i] = arr[i];
        }

        return whitelist;
    }
}

After some tests, it appears really inefficient because an array with 1,000,000 elements takes a very long time to end. Is there any better way to implement this on arrays?

Answer 1

You're following the same philosophy as the bubble sort, which is very, very, very slow. Have you tried this?:

• Sort your unordered array with quicksort. Quicksort is much faster than bubble sort (I know, you are not sorting, but the algorithm you follow is almost the same as bubble sort to traverse the array).
• Then start removing duplicates (repeated values will be next to each other). In a for loop you could have two indices: source and destination. (On each loop you copy source to destination unless they are the same, and increment both by 1). Every time you find a duplicate you increment source (and don't perform the copy).

Answer 2

Suggestion:

public static Integer[] removeDuplicates(Integer[] arr) {
  return new HashSet<Integer>(Arrays.asList(arr)).toArray(new Integer[0]);
}

Another solution might be:

public static int[] removeDuplicates(int[] arr) {
  Set<Integer> alreadyPresent = new HashSet<Integer>();
  int[] whitelist = new int[0];

  for (int nextElem : arr) {
    if (!alreadyPresent.contains(nextElem)) {
      whitelist = Arrays.copyOf(whitelist, whitelist.length + 1);
      whitelist[whitelist.length - 1] = nextElem;
      alreadyPresent.add(nextElem);
    }
  }

  return whitelist;
}

Here you only iterate once via arr.

Answer 3

A slight improvement on Dr H's

public static int[] removeDuplicates(int[] arr) {
    Set<Integer> alreadyPresent = new HashSet<>();
    int[] whitelist = new int[arr.length];
    int i = 0;

    for (int element : arr) {
        if (alreadyPresent.add(element)) {
            whitelist[i++] = element;
        }
    }

    return Arrays.copyOf(whitelist, i);
}

This does only one array copy at the end. It also takes advantage of the fact that Set.add() returns a boolean that indicated if the Set changed, and so avoids an explicit contains() check.

Java 8 update

In java 8 the code is a lot simpler :

public static int[] removeDuplicates(int[] arr) {
    return Arrays.stream(arr)
            .distinct()
            .toArray();
}