How to remove duplicate values in an array?

Answer 1

The simplest way of doing this is not very efficient, but provides a quick development time. You want to take all of the elements of the array, add them to a Set, then retrieve them as an array again. Note that this will probably not preserve the order of elements in the array.

{

Object[] originalArray; // let's pretend this contains the data that

// you want to delete duplicates from

Set newSet = new HashSet();

for (Object o : originalArray) {

newSet.add(o);

}

// originalArray is now equal to the array without duplicates

originalArray = newSet.toArray();

}

Now the efficient, and more correct, solution.

This one will create a new array of the correct size without duplicates.

{

Object[] originalArray; // again, pretend this contains our original data

// new temporary array to hold non-duplicate data

Object[] newArray = new Object[originalArray.length];

// current index in the new array (also the number of non-dup elements)

int currentIndex = 0;

// loop through the original array...

for (int i = 0; i < originalArray.length; ++i) {

// contains => true iff newArray contains originalArray[i]

boolean contains = false;

// search through newArray to see if it contains an element equal

// to the element in originalArray[i]

for(int j = 0; j <= currentIndex; ++j) {

// if the same element is found, don't add it to the new array

if(originalArray[i].equals(newArray[j])) {

contains = true;

break;

}

}

// if we didn't find a duplicate, add the new element to the new array

if(!contains) {

// note: you may want to use a copy constructor, or a .clone()

// here if the situation warrants more than a shallow copy

newArray[currentIndex] = originalArray[i];

++currentIndex;

}

}

// OPTIONAL

// resize newArray (using _newArray) so that we don't have any null references

String[] _newArray = new String[currentIndex];

for(int i = 0; i < currentIndex; ++i) {

_newArray[i] = newArray[i];

}

}

---------

The second version is correct in theory. However, if you deal with large two- or more- dimensional arrays, you are in trouble, as with each new element in the destination array you will have to search through a greater number of elements.

This is especially true if you look for duplicates in more than one element of the array, for example looking in columns 'a' and 'b' of array

a1 b1 c1 d1

a2 b2 c2 d2

a3 b3 c3 d3

Drop in performance is unbelievable if you go over approx 1,000 records with majority or records being unique.

I am trying to test a couple of different approaches for large arrays. If anyone is interested, let me know, and I will keep you posted.

Answer 2

Sort the array then test adjacent members for equality.