Sunday, September 1, 2013

An array of Numbers with Multiple Duplicates

How to Find Duplicates in an Array of N numbers ranging from 0 to N-1.

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 to find a duplicated number in such an 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.

Java Code:

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.");
}



No comments:

Post a Comment