重複整數

Question

我學習計算機科學，我一直在問這個問題：

長度的數組n + 1的填充範圍的整數[1，N]。在O（1）空間的線性時間內找到一個重複的整數（只有一個，不是全部）。該數組是隻讀的，可能不會被修改。變化：如果數組可能被寫入但必須保持未被算法修改，該怎麼辦？

如果有人能幫忙，那將會很棒。 謝謝

Answer 1

假設陣列是1索引：

n=size; 
x=a[n];y=a[a[n]]; 
while(x!=y)      
{ 
    x=a[x];y=a[a[y]]; 
} 
y=n; 
while(x!=y) 
{ 
    x=a[x];y=a[y]; 
} 
printf("DUPLICATE: %d",y); 

這種技術被稱爲波拉德的RHO方法。