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