如何在 O(n) 时间和 O(1) 空间的数组中查找重复项？

在 O(n) 时间和 O(1) 空间中查找重复项的高效算法

在本次编程挑战中，我们寻求一种高效的算法识别和打印整数数组中重复元素的算法，范围从 0 到 n-1，并可能重复。该挑战需要一种在 O(n) 时间复杂度内运行且仅消耗恒定内存空间的算法。

解决此问题的一种有效方法是“数组修改”技术。该算法的工作原理如下：

1. 第一个循环：

   • 初始化一个迭代数组中每个元素的循环，表示为A[i].
   • 对于每个A[i]，判断A[A[i]]是否等于A[i]。
   • 如果不等于，则将A[i]与A[交换A[i]].

2. 第二个循环：

   • 重置循环以迭代每个 A[i]再次。
   • 对于任何不等于 i 的 A[i]，打印 A[i]。此步骤识别重复元素，因为任何非重复元素的 A[A[i]] 都等于 i（即，它位于正确的位置）。

该算法的运行时间为 O(n)，因为每个元素在第一个循环中最多检查和修改一次。此外，由于没有使用额外的数据结构，因此它仅利用 O(1) 空间。

例如，考虑输入数组 {1, 2, 3, 1, 3, 0, 6}。运行算法后，数组将被修改如下：

[1, 2, 3, 1, 3, 0, 0]

第二个循环然后打印重复元素 1 和 3。

以上是如何在 O(n) 时间和 O(1) 空间的数组中查找重复项？的详细内容。更多信息请关注PHP中文网其他相关文章！