找出数组中任意一个重复的数字！
思路1:把数组排序，从排序后的数组中找出重复的数字。但排序一个长度为n的数组需要O(nlogn)的时间。
思路2:利用哈希表。从头到尾按顺序扫描数组每个数字，每次扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表是否已经包含了该数字，如果没有就添加到表中，如果有就返回。这个算法时间复杂度是O(n)，但他提高时间的效率是以一个大小为O(n)的哈希表为代价的，以空间换时间。
思路3:如果数组中没有重复的数字，那么当数组排序后数字i将出现在下标为i的位置。现在我们重排这个数组，从头到尾依次扫描每个数字，当扫描到下标为i的数字时，就先比较这个数字(用m表示)是不是等于i。如果是则继续扫描，如果不是则拿它和第m个数字进行比较。如果相等，就找到了一个重复的数字，如果不相等，就把第i个数字和第m个数字交换，接下来再重复比较、交换的过程，直到发现重复的数字。
代码如下：
bool duplicate(int numbers[],int length,int* duplicate)
{
if (numbers == nullptr || length <= 0)
{
return false;
}
for (int i = 0;i < length;++i)
{
if (numbers[i] < 0 || numbers[i] >length -1)
{
return false;
}
}
for (int i = 0;i < length;++i)
{
while (numbers[i] != i)
{
if (numbers[i] == numbers[numbers[i]])
{
*duplicate = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
上述代码中不需要额外分配内存，都是在原数组上进行的操作，空间复杂度为O(1)。代码中有一个两重循环，但每个数字最多只要交换两次就能找到自己的位置，所以总的时间复杂度为O(n)。
现在我们将题目改变一下条件。
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改数组本身。
思路1:由于不能修改原数组，我们可以新建一个辅助数组，然后逐一把原数组中的数字复制到辅助数组中。比如原数组中被复制的数字是m，那就把它复制到辅助数组下标为m的位置。这样很快就能找到哪个数字是重复的。需要O(n)的辅助空间。
思路2:为了避免空间开销，我们讨论一种更好的解决方法。采用类似二分查找的思想。把1～n的数字从中间数字m分成两部分，前面一部分为1～m，后面一部分为m+1～n。如果1~m的数字中出现的次数大于m，则说明此区间一定有重复的数字。
我们以数组{2,3,5,4,3,2,6,7}为例，根据题目要求，这个长度为8的数组中的所有数字都在1～7范围内。中间的数字4将1～7的范围分成两段，一段是1～4，一段是5～7，接下来我们统计1～4这4个数字在数组中出现的次数，它一共出现了5次，因此1～4中一定有重复的数字。接下来再把1～4的范围一分为二，一段是1，2两个数字，一段是3，4两个数字。再统计后发现第3个和第4个在数组中一共出现了3次，这意味着这两个数字中一定有一个重复了。我们分别再统计这两个数字在数组中出现的次数。
代码如下:
int getDuplication(const int* numbers,int length)
{
if (numbers == nullptr || length < 0)
{
return -1;
}
int start = 1;
int end = length - 1;
while (end >= start)
{
int middle = (end - start) / 2;
int count = countRange(numbers,length,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;
}
int countRange(const int* numbers,int length,int start,int end)
{
if (numbers == nullptr)
{
return 0;
}
int count = 0;
for (int i = 0;i < length; i++)
{
if (numbers[i] >= start && numbers[i] <= end)
{
++count;
}
}
return count;
}
注：需要指出的是，上述代码并不能保证找出重复的数字。例如上述例子中的1～2的范围里有1和2两个数字，这个范围的数字也出现里2次，但2是重复数字。
从上述分析中可以看出，如果面试官提不同的功能要求，那么我们最终选取的算法也将不同。
