如何以最佳时间和空间复杂度查找数组中的重复项？

以最佳时间和空间复杂度查找重复项

简介：
检测重复元素的任务数组是编程中的一个普遍问题。虽然使用哈希表等辅助数据结构的解决方案提供了简单性，但它们会损害空间效率。本文提出了一种巧妙的算法，可以在线性时间内识别重复项，O(n)，同时保持恒定的空间消耗，O(1)。

问题陈述：
给定一个数组从 0 到 n-1 的 n 个元素，其中某些数字可能出现多次，找出数组中重复的元素。

最优算法：

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

见解：
该算法利用了这样一个事实：数组中的每个元素理想情况下应位于其索引处。它使用数组的元素来创建排列，确保存在的元素将映射到其正确的索引。第一个循环迭代数组，并确保每个元素通过交换达到其预期索引。

解释：
第一个循环对数组进行排列，以便对于任何元素 x，如果它至少出现一次，一个实例将位于索引 A[x] 处。在每次交换中，都会更正与错误元素相对应的条目，从而保证交换总数受元素数量 N-1 的限制。

第二个循环通过打印每个元素的索引来识别重复项与索引不匹配的元素，表明它在原始数组中不存在。

结论：
该算法通过巧妙地利用输入数组，有效地识别数组中的重复元素本身。其 O(n) 时间复杂度和 O(1) 空间复杂度使其适合广泛的实际应用。

以上是如何以最佳时间和空间复杂度查找数组中的重复项？的详细内容。更多信息请关注PHP中文网其他相关文章！