在 O(n) 时间和 O(1) 空间中查找重复项：深入解释

提出的问题涉及识别重复项数组中包含 0 到 n-1 范围内的数字的元素。挑战在于如何在 O(n) 时间复杂度内并仅使用恒定 (O(1)) 内存空间有效地实现这一目标。

所提出的解决方案采用了一种巧妙的技术，不需要哈希表或其他附加数据结构。相反，它利用数组本身中的值来识别和标记重复元素。

1. 排列数组：

   内部循环排列基于以下逻辑的数组：

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   这一排列步骤确保如果数组中存在元素 x，则其至少一个实例将位于 A[x]。这对于后续步骤至关重要。

2. 识别重复项：

   外循环检查每个元素 A[i]:

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   如果 A[i] != i，则表示 i 没有出现在数组中正确的位置。因此，它是一个重复元素，并且被打印。

3. 时间复杂度分析：

   该技术运行时间为 O(n) 时间。嵌套循环有一个迭代 n 次的外循环和一个最多执行 n - 1 次迭代的内循环（因为每次交换都会使一个元素更接近其正确位置）。因此，迭代总数以 n*(n - 1) 为界，即 O(n^2)，但可以简化为 O(n)，因为 n*(n - 1) = n^2 - n = n(n - 1) = n*n - n

4. 空间复杂度分析:

   该算法仅使用恒定空间，与输入的大小无关。关键的见解是用于排列的空间已经存在于输入数组中。不需要额外的存储结构。

5. 附加说明：

   • 算法假设数组包含从0到n的整数 - 1.
   • 即使存在重复项，时间复杂度也保持不变。
   • 该算法对于小型到中等大小的数组非常有效。对于大型数组，使用哈希表等数据结构的替代方法可能更合适。