1-1000放在含有1001個(gè)元素的數(shù)組中，只有唯一的一個(gè)元素值重復(fù)，其它均只出現(xiàn)
一次。每個(gè)數(shù)組元素只能訪問一次，設(shè)計(jì)一個(gè)算法，將它找出來；不用輔助存儲(chǔ)空
間，能否設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)？
將1001個(gè)元素相加減去1,2,3,……1000數(shù)列的和，得到的差即為重復(fù)的元素。
int Find(int * a)
{
int i;//變量
for (i = 0 ;i<=1000;i++)
{
a[1000] += a[i];
}
a[1000] -= (i*(i-1))/2 //i的值為1001
return a[1000];
}
利用下標(biāo)與單元中所存儲(chǔ)的內(nèi)容之間的特殊關(guān)系，進(jìn)行遍歷訪問單元，一旦訪問過的單
元賦予一個(gè)標(biāo)記，利用標(biāo)記作為發(fā)現(xiàn)重復(fù)數(shù)字的關(guān)鍵。代碼如下：
void FindRepeat(int array[], int length)
{
int index=array[length-1]-1;
while ( true )
{
if ( array[index]<0 )
break;
array[index]*=-1;
index=array[index]*(-1)-1;
}
cout<<"The repeat number is "<<index+1<<endl;
}
此種方法不非常的不錯(cuò)，而且它具有可擴(kuò)展性。在壇子上有人提出：
對于一個(gè)既定的自然數(shù) N ，有一個(gè) N + M 個(gè)元素的數(shù)組，其中存放了小于等于 N 的所有
自然數(shù)，求重復(fù)出現(xiàn)的自然數(shù)序列{X} 。
對于這個(gè)擴(kuò)展需要，自己在A_B_C_ABC(黃瓜兒才起蒂蒂)的算法的基礎(chǔ)上得到了自己的算法
代碼：
按照A_B_C_ABC(黃瓜兒才起蒂蒂)的算法，易經(jīng)標(biāo)記過的單元在后面一定不會(huì)再訪問到，除非它是重復(fù)的數(shù)字，也就是說只要每次將重復(fù)數(shù)字中的一個(gè)改為靠近N+M的自然數(shù)，讓遍歷能訪問到數(shù)組后面的單元，就能將整個(gè)數(shù)組遍歷完。
代碼：
*/
void FindRepeat(int array[], int length, int num)
{
int index=array[length-1]-1;
cout<<"The repeat number is ";
while ( true )
{
if ( array[index]<0 )
{
num--;
array[index]=length-num;
cout<<index+1<<‘t‘;
}
if ( num==0 )
{
cout<<endl;
return;
}
array[index]*=-1;
index=array[index]*(-1)-1;
}
}
