Questions: All numbers in an array with length n+1 are in range from 1 to n, so there is at least one duplication in the
array. How to find any a duplication? Please don't modify the input array.
Analysis: The simple solution is to utilize
hash tables. When scanning the array, array elements are inserted into the hash
table one by one. In this way, it's easy to find a duplication with the hash
table, which costs O(n) space.
Let's try not to
employ extra space. Why there are duplications in the array? If there are no
duplications, the count of numbers ranging from 1 to n is n. Since the array
contains more than n numbers, there
should be duplications. It looks like it's important to count numbers in
ranges.
Let's divide numbers
from 1 to n into two ranges, split with
the number in the middle (denoted as m),
and then count the numbers of the two subranges. If the count of numbers from 1
to m is greater than m, the duplication is in the range from 1 to m. Otherwise, there should be at least one
duplication in the range from m+1 to n. And then we continue the recursive process
until we find the duplication.
The Java code is
listed below:
static int
countRange(int[] numbers, int start, int
end)
{
int count = 0;
for(int
i = 0; i < numbers.length; i++)
if(numbers[i] >= start &&
numbers[i] <= end)
++count;
return count;
}
static int
getDuplication(int[] numbers)
{
int start = 1;
int end = numbers.length;
while(end >= start)
int middle = ((end - start) >>
1) + start;
int count = countRange(numbers,
start, middle);
if(end == start) {
if(count > 1)
return start;
else
break;
}
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
The code with unit
tests is shared at http://ideone.com/lhV22m.
More coding interview questions are discussed
in my book< Coding Interviews: Questions, Analysis & Solutions>. You
may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of
this post. If you are going to use part of or the whole of this article in your
blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books,
please contact the author via zhedahht@gmail.com . Thanks.
