数组重复元素查找问题是否存在O(n)时间复杂度解法？

我在GeeksforGeeks平台完成「查找数组中的重复元素」算法题时，自己编写的解法虽然通过了所有测试用例，但由于调用了.sort()方法，我清楚它不符合题目要求的O(n)期望时间复杂度：没有通用排序算法能达到O(n)时间复杂度，即便是Python内置采用的Timsort（Python默认排序算法）最优实现也做不到。于是我查看了网站给出的参考答案，代码如下：

def printRepeating(arr, n):

# First check all the
    # values that are
# present in an array
    # then go to that
# values as indexes
    # and increment by
# the size of array
for i in range(0, n):
    index = arr[i] % n
    arr[index] += n

# Now check which value
    # exists more
# than once by dividing
    # with the size
# of array
for i in range(0, n):
    if (arr[i]/n) >= 2:
        print(i, end=" ")

我尝试梳理该算法的底层逻辑但没能完全理解，于是使用多组测试数据集验证，发现该解法在部分场景下运行失败。例如测试数组为arr = [5, 6, 3, 1, 3, 6, 6, 0, 0, 11, 11, 1, 1, 50, 50]时，代码输出结果为0 1 3 5 6 11 13 14。

该结果存在三处明显错误：

• 数字5在数组中仅出现1次并未重复，却被判定为重复元素；
• 数字13和14根本不存在于原数组中，却被误判为重复元素；
• 数字50在数组中存在且重复，但该解法并未将其识别输出。

我已经向网站反馈了该题解的问题，考虑到这类题目属于官方精选题库内容，我想确认该问题是否真的存在O(n)时间复杂度的解法？我个人猜测除非能在键值映射结构中以O(1)时间完成每个重复数字的插入操作，否则不存在这样的解法。

解答 #

你发现的题解错误完全属实，这个挂在网站上的参考答案遗漏了最核心的适用前提：该算法仅在数组所有元素的取值范围落在[0, n-1]区间（n为数组长度）时才能正常工作，根本不是通用解法。
你测试用例里的数组长度是15，但出现了50这种远大于14的元素，计算arr[i] % n时得到的索引完全错误，自然会出现不存在的元素被误判、超出范围的重复元素漏检的问题。

关于O(n)复杂度解法是否存在，要分两种场景讨论：

• 如果题目明确给出值域约束（所有元素为0到n-1之间的整数）：这类场景是存在严格O(n)时间、O(1)额外空间的解法的，也就是题解想实现的原地索引计数思路。逻辑也很简单：因为元素值都在索引范围内，遍历数组时给对应索引位置的元素值加上数组长度n，这个操作不会丢失原始值信息——通过arr[i] % n就能还原该位置存储的原始数值，而arr[i] // n的结果就等于对应索引值被访问的次数，结果≥2就说明该值重复。只是公开的题解代码没有做边界校验，也没说明适用前提，才会在通用场景下出错。
• 如果题目没有值域约束，元素可以是任意整数：你的猜测完全正确，不存在严格O(n)时间、O(1)额外空间的通用解法。这种场景下只有两类可行方案：
  • 用哈希表（键值映射结构）遍历计数，时间复杂度O(n)，但需要O(n)的额外空间存储哈希表；
  • 先排序再遍历找相邻重复值，额外空间可以做到O(1)，但时间复杂度为O(nlogn)。
    两类方案必须在时间和空间上做权衡，没有能同时满足O(n)时间、O(1)额外空间的通用解法。

内容的提问来源于stack exchange，提问作者Carlos Ortega González