如何在 O(n) 时间和 O(1) 空间内找到从 0 到 n-1 的数字数组中的重复项？

在 O(n) 时间和 O(1) 空间中查找重复项

给定一个包含 n 个元素的数组，其中包含从 0 到 n 的数字-1，其中某些数字可能会出现多次，目标是在 O(n) 时间内找到重复元素并使用恒定的内存空间。

为了实现这一点，我们可以利用一种有趣的方法，该方法不会不需要哈希表等额外的数据结构。

建议的算法操作如下：

1. 排列循环：

   • 从 0 到 n-1 迭代 i 的数组。
   • 在此循环内，执行以下步骤，直到 A[A[i]] 等于 A[i]。这意味着元素 A[i] 处于正确的位置。
   • 将 A[i] 与 A[A[i]] 交换。这有效地将元素 A[i] 向正确位置移动了一步。

2. 重复识别循环：

   • 再次遍历数组，从 i 从 0 到 n-1。
   • 如果 A[i] 不等于 i，则意味着索引 A[i] 处有 i 的重复项。
   • 将 A[i] 打印为重复项。

此算法可确保识别所有重复元素。外循环运行n次，内循环最多运行n-1次。因此，该算法的运行时间为 O(n)。它不使用任何额外的数据结构，这意味着它在 O(1) 空间中运行。

提供的代码示例了该算法在 C 中的实现。

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