输入:给定n个元素的数组,其中包含从0到n-1的元素,这些数字中的任何一个都会出现任意次数.
目标:在O(n)中找到这些重复数字并仅使用常量存储空间.
例如,设n为7,数组为{1,2,3,1,3,0,6},答案应为1和3.我在这里检查了类似的问题,但答案使用了一些数据结构等HashSet.
任何有效的算法都相同？
caf*_*caf 163
这就是我提出的,不需要额外的符号位:
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
第一个循环置换数组,以便if元素x至少存在一次,那么其中一个条目将处于位置A[x].
请注意,它可能看起来不是O(n)乍一看,但它是 - 尽管它有一个嵌套循环,它仍然会O(N)及时运行.只有在存在i这样的情况下才会发生交换A[i] != i,并且每个交换设置至少一个元素,使得A[i] == i之前的情况不成立.这意味着交换的总数(以及while循环体的总执行次数)最多N-1.
第二环路打印的值x对其A[x]不等于x-由于第一循环保证,如果x阵列中的至少一次存在,其中的一个实例将在A[x],这意味着它的打印那些值x中不存在在数组.
j_r*_*ker 35
caf的精彩答案打印出在阵列中出现k次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].显而易见的是,我们make(A[A[i]] = i)的改变将m通过导致其if条件的下半部分失败来防止其他非家庭事件作为重复输出,但是当它i到达本地位置时它会工作m吗？是的,它会,因为现在,即使在这个新的i我们发现if条件的前半部分A[i] != i是真的,下半部分测试它指向的位置是否是一个家庭位置并且发现它不是.在这种情况下,我们已经不知道是否m或A[m]为重复的值,但我们知道,无论哪种方式,它已经被报道,因为这2个周期保证不会出现在咖啡馆的第一环的结果.(注意,如果m != A[m]那么恰好其中一个m并且A[m]多次出现,而另一个则根本不出现.)
Pra*_*rav 22
这是伪代码
for i <- 0 to n-1:
if (A[abs(A[i])]) >= 0 :
(A[abs(A[i])]) = -(A[abs(A[i])])
else
print i
end for