arrays - 是否可以使用 Floyd 的龟兔算法在 O(n) 时间、O(1) 空间复杂度内从未排序的数组中删除重复项？

Question

是否可以使用 Floyd 的龟兔算法在 O(n) 时间、O(1) 空间复杂度内从未排序的数组中删除重复项？考虑数组 [3,1,3,4,2]。删除重复项后，函数“remove_dups”必须返回 [3,1,4,2]。此外，该函数应该对数组中的负整数起作用。

Answer 1

对的，这是可能的。这个想法是将数组项视为链表节点。任何特定索引都指向该索引处的值。

你会看到在重复的情况下存在循环，两个索引将具有相同的值，并且它们将形成一个循环，如下图所示。

例子：

1->2->3->4->5->6->3

所以我们可以在链表中找到循环的入口点，这将是我们的重复元素。

来源：https ://www.geeksforgeeks.org/find-duplicates-constant-array-elements-0-n-1-o1-space/