在 1 到 N−1 范围内找出重复整数的高效算法Finding a duplicated item in an array of N integers in the range 1 to N − 1

一位同事告诉我，存在一种 O(N) 算法，可以在范围从 1 到 N−1 的 N 个整数数组中找到重复项。根据鸽巢原理，由于数组长度与数值范围不一致，必然存在重复值。可能存在多个重复值，只需找出任意一个即可。

这个谜题的背景是，我的同事原本认为该问题可以通过排序后扫描来求解，时间复杂度为 O(N log N)。于是他把这个问题作为面试题提出，而面试者竟然找到了一个更优的线性时间算法！

我的解法是将数组视为基于 1 的索引链表，并利用每个整数的符号位作为标记，表示该位置是否已被访问。我们从索引 1 开始，沿着索引跳转，直到遇到符号位已被设置的值（即重复项），或者回到索引 1（形成环）。如果检测到环，则移动到下一个未设置符号位的索引并重复此过程。最后，通过清除符号位即可恢复原始数值。

我认为修改数值是可以接受的，因为 O(N log N) 的解法也需要对数组进行排序操作。至少我的方法在完成后能还原原始数据！

但事实上，那位面试候选人发现了一个更优的 O(N) 算法——它完全不需要修改数组。

再次将数组值视为索引。我们正在寻找两个指向同一目标的节点。已知没有任何数组元素包含值 N，因此索引 N 处的元素不可能属于某个环。这意味着从索引 N 开始的链最终必然会接入已有的环，而这个接入点就是重复项。从索引 N 出发，使用 Floyd 循环检测算法可在 O(N) 时间内找到环的起点。

¹ 如果进一步限定问题条件为仅有一个重复值，则可通过求和所有数值，再减去 N(N−1)/2 得到重复项。

² 我耍了个小把戏。实际上这是 O(N) 空间复杂度的，因为我利用符号位作为方便的“初始为零”标志位。

分类

主题

作者

Raymond 参与 Windows 系统演进已超过 30 年。2003 年起，他创办了名为 The Old New Thing 的网站，其受欢迎程度远超他的想象，至今仍让他感到些许不安。该网站催生了一本同名书籍《The Old New Thing》（Addison Wesley, 2007）。他偶尔会在 Windows Dev Docs Twitter 账号上出现，讲述一些毫无实用价值的故事。