是什麼指針加倍在Java數組的背景是什麼意思？

查找重複的。給出N + 1元件的陣列，其中每個元素是1和N之間的整數，寫一個算法來找到重複。你的算法應該以線性時間運行，使用O（1）額外的空間，並且不得修改原始數組。提示：指針加倍。是什麼指針加倍在Java數組的背景是什麼意思？

我試圖從一本書上解決這個問題。指針加倍在這種情況下意味着什麼？書中使用Java，所以我假定這必須適用的東西到Java以及即使沒有在Java中指針的概念。

2011-05-04 Pan

我不認爲我可以在該網頁上添加任何東西超出了內容：

你實際的O問題（n）的運行時間和O（1）空間大約一半，解決該頁面，以及我認爲必須將「指針加倍」作爲最佳解決方案。解決問題的基本僞代碼給出：

let i ← n, j ← n 
do: i ← A[i], j ← A[A[j]]; until i = j 
set j ← n 
do: i ← A[i], j ← A[j]; until i = j 
return i

雖然我會建議您訪問該網站的解釋是比任何我可以給更徹底。

2011-05-04 21:55:32

-1用於解決問題，而不是回答問題。 – eggyal 2011-05-04 22:10:01

我不知道什麼指針加倍正式意味着，但通過使用數組中的每個元素作爲計數器和值，你可以解決這個問題。我故意不提供完整的解決方案，因爲我懷疑你想自己弄清楚。

一個提示：數組中的所有數字都是整數，但是是正數。你知道N < MAX_INT。你可以利用這個優勢嗎？

2011-05-04 22:05:40

回答