Skip to content
May 5, 2011 / oop123

Removing Duplicates From An Array in Java – Sort And Remove

Another way to remove duplicates from an array is to sort the array (if you don’t want to change the first array, then you need to create a copy of the array first); after the sort, all the duplicates in the array will be together, and you can then just iterate through the array to find the unique elements. The sorting algorithm needs to be fast for this method to be of any use. Luckily, the JDK already has a fast Arrays.sort(), and there is no need to reinvent the wheel.

The following code is a function for removing duplicates from an int array.

public static int[] removeDuplicatesWithSort(int[] array) {
        if (array == null || array.length == 0) { return array; }

        //create a sorted copy
        int[] copy = Arrays.copyOf(array, array.length);
        Arrays.sort(copy);

        //remove the duplicates -> they will be together
        int count = 0;
        int previous = copy[0];
        for (int i = 1; i < array.length; ++i) {
            if (previous != copy[i]) {
                previous = copy[i];
                copy[++count] = previous;
            }
        }

        return Arrays.copyOf(copy, count + 1);
}

A generic method using sort and remove would look something like this (again, I’m new to Java, so it can suck/not work):

@SuppressWarnings({"unchecked"})
public static <T extends Comparable<T>> T[] sortAndRemoveDuplicates(T[] array) {
        if (array == null || array.length == 0) return array;

        //create a sorted copy
        T[] copy = Arrays.copyOf(array, array.length);
        Arrays.sort(copy);

        //remove the duplicates -> they will be together
        int count = 0;
        T previous = copy[0];
        
        for (int i = 1; i < array.length; ++i) {
            //deal with possible nulls - skip through them
            if (previous == null) {
                for (; copy[i] == null && i < array.length; i++);
            }

            else if (previous.compareTo(copy[i]) != 0) {
                previous = copy[i];
                copy[++count] = previous;
            }
        }

        return Arrays.copyOf(copy, count + 1);
}

It’s pretty much the exact same as the int array method. Note that since the method uses Arrays.sort(), the Class T in the method needs to implement the Comparable interface.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: