在 O(n) 时间和 O(1) 空间中查找重复项 [英] Finding duplicates in O(n) time and O(1) space

问题描述

输入:给定一个由 n 个元素组成的数组，其中包含从 0 到 n-1 的元素，这些数字中的任何一个出现任意次数.

目标:在 O(n) 中找到这些重复的数字，并且只使用恒定的内存空间.

例如，设 n 为 7，数组为 {1, 2, 3, 1, 3, 0, 6}，则答案应为 1 &3.我在这里检查了类似的问题，但答案使用了一些数据结构，如 HashSet 等.

有什么有效的算法吗?

解决方案

这是我想出来的，不需要额外的符号位:

for i := 0 to n - 1而 A[A[i]] != A[i]交换(A[i]，A[A[i]])结束时结束于对于 i := 0 到 n - 1如果 A[i] != i 那么打印 A[i]万一结束于

第一个循环对数组进行置换，以便如果元素 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 的那些值代码> 不存在于数组中.

(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)

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