問題描述
輸入:給定一個(gè)由 n 個(gè)元素組成的數(shù)組，其中包含從 0 到 n-1 的元素，這些數(shù)字中的任何一個(gè)出現(xiàn)任意次數(shù).
目標(biāo):在 O(n) 中找到這些重復(fù)的數(shù)字，并且只使用恒定的內(nèi)存空間.
例如，設(shè) n 為 7，數(shù)組為 {1, 2, 3, 1, 3, 0, 6}，則答案應(yīng)為 1 &3.我在這里檢查了類似的問題，但答案使用了一些數(shù)據(jù)結(jié)構(gòu)，如 HashSet 等.
有什么有效的算法嗎?
這是我想出來的，不需要額外的符號位:
for i := 0 to n - 1而 A[A[i]] != A[i]交換(A[i]，A[A[i]])結(jié)束時(shí)結(jié)束于對于 i := 0 到 n - 1如果 A[i] != i 那么打印 A[i]萬一結(jié)束于第一個(gè)循環(huán)對數(shù)組進(jìn)行置換，以便如果元素 x 至少出現(xiàn)一次，那么其中一個(gè)條目將位于 A[x] 位置.
請注意，乍一看它可能不是 O(n)，但確實(shí)如此 - 盡管它有一個(gè)嵌套循環(huán)，但它仍然在 O(N) 時(shí)間內(nèi)運(yùn)行.交換僅在存在 i 使得 A[i] != i 時(shí)發(fā)生，并且每個(gè)交換設(shè)置至少一個(gè)元素使得 A[i]== i，以前不是這樣.這意味著交換的總數(shù)(以及 while 循環(huán)體的執(zhí)行總數(shù))最多為 N-1.
第二個(gè)循環(huán)打印 x 的值，其中 A[x] 不等于 x - 因?yàn)榈谝粋€(gè)循環(huán)保證如果 x 在數(shù)組中至少存在一次，其中一個(gè)實(shí)例將位于 A[x]，這意味著它會打印 x 的那些值代碼> 不存在于數(shù)組中.
(Ideone 鏈接，您可以使用它)
Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.
Goal : To find these repeating numbers in O(n) and using only constant memory space.
For example, let n be 7 and array be {1, 2, 3, 1, 3, 0, 6}, the answer should be 1 & 3.
I checked similar questions here but the answers used some data structures like HashSet etc.
Any efficient algorithm for the same?
This is what I came up with, which doesn't require the additional sign bit:
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
The first loop permutes the array so that if element x is present at least once, then one of those entries will be at position A[x].
Note that it may not look O(n) at first blush, but it is - although it has a nested loop, it still runs in O(N) time. A swap only occurs if there is an i such that A[i] != i, and each swap sets at least one element such that A[i] == i, where that wasn't true before. This means that the total number of swaps (and thus the total number of executions of the while loop body) is at most N-1.
The second loop prints the values of x for which A[x] doesn't equal x - since the first loop guarantees that if x exists at least once in the array, one of those instances will be at A[x], this means that it prints those values of x which are not present in the array.
(Ideone link so you can play with it)
這篇關(guān)于在 O(n) 時(shí)間和 O(1) 空間中查找重復(fù)項(xiàng)的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！