輸入：給定n個元素組成的數組，其中包含從0到n-1的元素，這些數字中的任何一個出現任何次數。目標：在O（n）中查找這些重復數字，并且僅使用恒定的存儲空間。例如，假設n為7，數組為{1、2、3、1、3、0、6}，答案應該為1和3。我在這里檢查了類似的問題，但答案使用了諸如HashSetetc之類的一些數據結構。有沒有同樣有效的算法？
3 回答
紅顏莎娜
TA貢獻1842條經驗 獲得超13個贊
這是我想出的，不需要額外的符號位：
for i := 0 to n - 1
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 0 to n - 1
if A[i] != i then
print A[i]
end if
end for
第一個循環對數組進行排列，因此，如果element x至少存在一次，則這些條目之一將位于position A[x]。
請注意，乍一看它看起來可能不是O（n），但它是-盡管具有嵌套循環，但仍會O(N)及時運行。僅當存在一個i這樣的時，才會發生交換A[i] != i，并且每個交換都將至少一個元素設置為A[i] == i，這樣以前是不正確的。這意味著交換的總數（以及while循環體的執行總數）最多為N-1。
第二環路打印的值x對其A[x]不等于x-由于第一循環保證，如果x存在至少一次陣列中，其中的一個實例將在A[x]，這意味著它打印的那些值x中不存在在數組。
莫回無
TA貢獻1865條經驗 獲得超7個贊
caf出色的答案將打印出現在數組k-1次中k次的每個數字。這是有用的行為，但是這個問題可以說要求每個副本僅打印一次，并且他暗示了這樣做的可能性而不會超出線性時間/恒定空間界限。這可以通過用以下偽代碼替換他的第二個循環來完成：
for (i = 0; i < N; ++i) {
if (A[i] != i && A[A[i]] == A[i]) {
print A[i];
A[A[i]] = i;
}
}
這利用了第一個循環運行之后的屬性，如果任何值m出現多次，則保證其中一個出現在正確的位置，即A[m]。如果我們小心的話，我們可以使用該“主頁”位置來存儲有關是否已打印任何副本的信息。
在caf的版本中，當我們遍歷數組時，A[i] != i暗示這A[i]是重復的。在我的版本中，我依賴于一個稍有不同的不變式：這A[i] != i && A[A[i]] == A[i]意味著這A[i]是我們之前從未見過的重復項。（如果刪除“我們之前從未見過的”部分，那么其余部分可以被認為是caf不變式的真相，并且保證所有重復項在原位都有一些副本。）一開始（在caf的第一個循環完成之后），下面我顯示它在每個步驟之后都得到維護。
當我們遍歷數組時，A[i] != i測試的成功意味著A[i] 可能是以前從未見過的重復。如果我們以前從未看過它，那么我們希望A[i]的原位指向自己-這是在if條件的后半部分進行測試的結果。如果是這種情況，我們將其打印出來并更改家庭位置，使其指向該首次發現的重復項，從而創建一個兩步的“循環”。
要查看此操作不會改變我們的不變，假設m = A[i]一個特定的位置i滿足A[i] != i && A[A[i]] == A[i]。顯然，我們所做的（A[A[i]] = i）更改將m通過使if條件的后半部分條件失敗來防止其他非住宅出現作為重復輸出而起作用，但是i到達住宅位置是否起作用m？是的，因為現在，即使新i發現if條件的第一個一半A[i] != i為真，第二個一半也會測試它所指向的位置是否為家中位置，而發現不是。在這種情況下，我們已經不知道是否m或A[m]為重復的值，但我們知道，無論哪種方式，由于已經保證了這2個循環不會出現在caf的第一個循環的結果中，因此已經有報道。（請注意，如果m != A[m]恰好其中一個m和A[m]發生多次，而另一個根本不發生。）
- 3 回答
- 0 關注
- 689 瀏覽
添加回答
舉報
0/150
提交
取消