A solution is to sort the array taking advantage of the fact that if
the contents are in fact a permutation of the values 0..n-1, value x
always goes in position A[x]. Therefore you can immediately swap value
x into the correct position. If that position already contains value
x, you have identified a duplicate.
bool hasDuplicate(int *a, int n)
{
for(int i = 0; i < n; ++i)
{
while(a[i] != i)
{
int j = a[i];
if (a[j] == j) return true;
a[i] = a[j];
a[j] = j;
}
}
return false;
}
At first it may appear to be O(n^2) but notice that each pass through
the inner loop puts one value in its correct place. Thus the inner
loop executes at most n times. Unlike a similar solution above, if it
finds a duplicate it immediately returns, so in some cases it doesn't
require n iterations.
This solution is also faster than the solution using the sign bit,
based on a benchmark test I ran.
Don
On Oct 30, 2:27 pm, Don <[email protected]> wrote:
> Given an array of N integers in the range 0..N-1, determine if any
> number is repeated in the array.
> Solution should execute in O(n) time and use constant space.
> Don
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
