在O（n）时间及O（1）空间查找重复 [英] Finding duplicates in O(n) time and O(1) space

问题描述

输入：给定n个元素的数组，它包含的元素从0到n-1，用任何出现任意次数这些数字。

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.

目标：要查找在O（n）和使用唯一不变的内存空间，这些重复号

Goal : To find these repeating numbers in O(n) and using only constant memory space.

例如，令n为7和阵列是{1，2，3，1，3，0,6}，答案应该是1安培; 3。 我在这里签类似的问题，但答案中使用的一些数据结构，如的HashSet 等

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

第一个循环permutes阵列，这样，如果元素 X 是present至少一次，然后将这些条目之一将是在位置 A [X] 。

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].

请注意，它可能不看为O（n）乍一看，但它是 - 虽然它有一个嵌套的循环，它仍然在 O（N）运行时间。一个交换只发生，如果有一个我，使得 A [1]！=我，并且每个交换内置至少一个元件，使得 A [1] = =我，其中那是不正确的了。这意味着，互换的总数（因此，而循环体的执行死刑的总数）最多为 N-1 。

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.

第二个循环打印 X 为其 A [X] 不等于<$ C的值$ C> X - 以来的首次环保证，如果 X 至少存在一次阵列中，其中的一个实例将在 A [X] ，这意味着它打印的 X 不属于present阵列中的

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链接，使您可以用它玩）

这篇关于在O（n）时间及O（1）空间查找重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！