有一個數(shù)組長度為N,里面的N個數(shù)的范圍是[1, N-1]，因此必有數(shù)是重復出現(xiàn)的。求一個算法找出這個數(shù)，要求時間復雜度為O(n),空間復雜度為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);
}