Finding duplicates in array…


An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the
array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you
find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5,
3}, the implemented function (or method) should return either 2 or 3.

Indexes in an array with length n are in the range 0 to n-1. If there were no duplication in the n
numbers ranging from 0 to n-1, we could rearrange them in sorted order, locating the number i as the ith
number. Since there are duplicate numbers in the array, some locations are occupied by multiple
numbers, but some locations are vacant.
Now let’s rearrange the input array. All numbers are scanned one by one. When the ith number is
visited, first it checks whether the value (denoted as m) is equal to i. If it is, we continue to scan the next
number. Otherwise, we compare it with the mth number. If the ith number equals the mth number,
duplication has been found. If not, we locate the number m in its correct place, swapping it with the mth
number. We continue to scan, compare, and swap until a duplicated number is found.
Take the array {2, 3, 1, 0, 2, 5, 3} as an example. The first number 2 does not equal its index 0, so it is
swapped with the number with index 2. The array becomes {1, 3, 2, 0, 2, 5, 3}. The first number after
swapping is 1, which does not equal its index 0, so two elements in the array are swapped again and the
array becomes {3, 1, 2, 0, 2, 5, 3}. It continues to swap since the first number is still not 0. The array is {0,
1, 2, 3, 2, 5, 3} after swapping the first number and the number with index 3. Finally, the first number
becomes 0.
Let’s move on to scan the next numbers. Because the following three numbers, 1, 2 and 3, are all
equal to their indexes, no swaps are necessary for them. The following number, 2, is not the same as its
index, so we check whether it is the same as the number with index 2. Duplication is found since the
number with index 2 is also 2.


int duplicate(int numbers[]) {
int length = numbers.length;
for(int i = 0; i < length; ++i) {
if(numbers[i] < 0 || numbers[i] > length - 1)
throw new IllegalArgumentException("Invalid numbers.");
}
for(int i = 0; i < length; ++i) {
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
// swap numbers[i] and numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
throw new IllegalArgumentException("No duplications.");
}

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