感谢您花时间回答一个非常简单的问题。我最近遇到了一个编码挑战，在优化之后，我做了一个算法，我确信它不起作用，但找不到一个测试用例来打破它。能有比我更有经验的人给我一个不能工作的测试用例吗?你能证实这个算法是O(n)时间和O(1)空间复杂度吗?问题在这里。
挑战:
编写一个算法，从整数数组中返回一个重复的整数。该数组的构造使得每个整数都大于1(包含)且小于数组长度(不包含)。
输入:
一个大小为N的整数数组，其中每个整数x都遵循1 <= x
输出:
在输入中重复的整数。
例子:
输入:[1,2,3,1]
输出:1
输入:[2,3,4,2,4]
输出:2或4
不应该工作的算法:
def find_duplicates(arr):
curr_n = arr[0]
while True:
removed_n = arr[curr_n]
if removed_n == curr_n:
return curr_n
arr[curr_n] = curr_n
curr_n = removed_n
你的算法是O(n)。
每次迭代，它为某个索引i设置arr[i] = i，或者在arr[i] == i已经存在时停止。它只能修复O(n)个索引，因此需要O(n)个时间。
你的算法也工作。事实上，它相当不错。
如果我们认为一个数字"在正确的位置"当arr[i] == i时，那么在循环的每次迭代开始时，我们知道我们从错误的位置得到curr_n。我们在第一次迭代中就知道了这一点，因为数组中没有0，所以arr[0]总是在错误的位置。对于后续的迭代，我们知道这一点，因为我们检查了if removed_n == curr_n。
所以我们知道curr_n来自一个错误的地方。如果在右边的位置也找到相同的数字，则它是重复的，并返回它。
如果你只是改变变量名，它是如何工作的就变得更清楚了:
def find_duplicate(arr):
misplaced = arr[0]
while True:
replacing = arr[misplaced]
if replacing == misplaced:
return misplaced
arr[misplaced] = misplaced
misplaced = replacing
周期检测方法
def duplicate(arr):
slow = arr[arr[0]]
fast = arr[arr[arr[0]]]
while slow != fast:
slow = arr[slow]
fast = arr[arr[fast]]
fast = arr[0]
while slow != fast:
slow = arr[slow]
fast = arr[fast]
return slow