### 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 thearray. 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