有一個(gè)數(shù)組長(zhǎng)度為N,里面的N個(gè)數(shù)的范圍是[1, N-1]，因此必有數(shù)是重復(fù)出現(xiàn)的。求一個(gè)算法找出這個(gè)數(shù)，要求時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[]={1,2,4,3,6,3,4};
int tmp,tmp2;
tmp=a[0];
while(1)
{
if(a[tmp]!=-1)
{
tmp2=a[tmp];
a[tmp]=-1;
tmp=tmp2;
}
else break;
}
printf("%d\n",tmp);
}