《剑指offer》:[51]数组中的重复数字
栏目：php教程时间：2016-08-22 09:16:56
题目：在1个长度为n的数组里所有数字都在0到n⑴的范围里。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每一个数字重复几次。请找出数组中任意1个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那末对应的输出是重复的数字2或3.
分析：其实这个题由于它的限制太多，这样是这个题失去了泛型，比如里面的数字的范围肯定在0到n⑴内，还有任意意对便可，不能对任意的数组进行查重操作。下面先来看看这个问题怎样解决吧！
方案1：时间复杂度为O(N*N)的顺序扫描法。从第1个扫描到最后，顺次进行第2个....1定能找出。
方案2：时间复杂度为O(N)+辅助空间O(N)的哈希表。将每一个数映照到哈希表，扫描1遍能统计出所有数字出现的次数。然后扫描哈希表能在O(1)的时间内得到该数据出现的次数。这样便能找到重复的数字了。
方案3：时间复杂度为0(N)，并且不要辅助空间。
思想是这样的：顺序扫描数组的每一个数字。当扫描到下标为i的数字时，比较该数字M是否是与下标i相等，如等，扫描下1个；如不等，再把它M和下标为M的数字相比较，如果相等，则找到1个返回；如果不等，则交换它们的值。
分析：其实这个题由于它的限制太多，这样是这个题失去了泛型，比如里面的数字的范围肯定在0到n⑴内，还有任意意对便可，不能对任意的数组进行查重操作。下面先来看看这个问题怎样解决吧！
方案1：时间复杂度为O(N*N)的顺序扫描法。从第1个扫描到最后，顺次进行第2个....1定能找出。
方案2：时间复杂度为O(N)+辅助空间O(N)的哈希表。将每一个数映照到哈希表，扫描1遍能统计出所有数字出现的次数。然后扫描哈希表能在O(1)的时间内得到该数据出现的次数。这样便能找到重复的数字了。
方案3：时间复杂度为0(N)，并且不要辅助空间。
思想是这样的：顺序扫描数组的每一个数字。当扫描到下标为i的数字时，比较该数字M是否是与下标i相等，如等，扫描下1个；如不等，再把它M和下标为M的数字相比较，如果相等，则找到1个返回；如果不等，则交换它们的值。
以数组a[7]={2,3,1,0,2,5,3}为例，分析以下图所示：
#include <iostream>
using namespace std;
int arr[7]={2,3,1,0,2,5,3};
void Swap(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
bool duplicate(int array[],int length,int *duplication)
{
if(array==NULL || length<0)
return false;
for(int i=0;i<length;i++)
{
if(array[i]<0 || array[i]>length⑴ )
return false;
}
for(int i=0;i<length;++i)
{
while(array[i]!=i)
{
if(array[i]==array[array[i]])
{
*duplication=array[i];
return true;
}
Swap(array[i],array[array[i]]);
}
}
return false;
}
int main()
{
int result;
bool res;
res=duplicate(arr,7,&result);
if(res)
cout<<"重复的数是："<<result<<endl;
else
cout<<"数据里没有重复的数！"<<endl;
system("pause");
return 0;
}
运行结果：
------分隔线----------------------------
------分隔线----------------------------