《劍指offer》:[51]數(shù)組中的重復(fù)數(shù)字
來源：程序員人生 發(fā)布時(shí)間：2016-08-22 09:16:56 閱讀次數(shù)：3007次
題目：在1個(gè)長度為n的數(shù)組里所有數(shù)字都在0到n⑴的范圍里。數(shù)組中某些數(shù)字是重復(fù)的，但是不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每一個(gè)數(shù)字重復(fù)幾次。請找出數(shù)組中任意1個(gè)重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那末對應(yīng)的輸出是重復(fù)的數(shù)字2或3.
分析：其實(shí)這個(gè)題由于它的限制太多，這樣是這個(gè)題失去了泛型，比如里面的數(shù)字的范圍肯定在0到n⑴內(nèi)，還有任意意對便可，不能對任意的數(shù)組進(jìn)行查重操作。下面先來看看這個(gè)問題怎樣解決吧！
方案1：時(shí)間復(fù)雜度為O(N*N)的順序掃描法。從第1個(gè)掃描到最后，順次進(jìn)行第2個(gè)....1定能找出。
方案2：時(shí)間復(fù)雜度為O(N)+輔助空間O(N)的哈希表。將每一個(gè)數(shù)映照到哈希表，掃描1遍能統(tǒng)計(jì)出所有數(shù)字出現(xiàn)的次數(shù)。然后掃描哈希表能在O(1)的時(shí)間內(nèi)得到該數(shù)據(jù)出現(xiàn)的次數(shù)。這樣便能找到重復(fù)的數(shù)字了。
方案3：時(shí)間復(fù)雜度為0(N)，并且不要輔助空間。
思想是這樣的：順序掃描數(shù)組的每一個(gè)數(shù)字。當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)，比較該數(shù)字M是否是與下標(biāo)i相等，如等，掃描下1個(gè)；如不等，再把它M和下標(biāo)為M的數(shù)字相比較，如果相等，則找到1個(gè)返回；如果不等，則交換它們的值。
以數(shù)組a[7]={2,3,1,0,2,5,3}為例，分析以下圖所示：
具體實(shí)現(xiàn)代碼以下：
#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<<"重復(fù)的數(shù)是："<<result<<endl;
else
cout<<"數(shù)據(jù)里沒有重復(fù)的數(shù)！"<<endl;
system("pause");
return 0;
}
運(yùn)行結(jié)果：
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
