这个(find + sort)问题能在O(n)内解决吗?

Question

我在geeksforgeeks.com上经历了这个问题，虽然我的解决方案设法通过了所有的测试用例，但我实际上使用了。sort()，所以我知道它不适合O(n)的预期时间复杂度:我的意思是我们都知道没有排序算法在O(n)上工作，甚至不是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 13 5 6 11 13 14

注意:

1. 数字5在数组中不重复，
2. 数字13和14甚至不存在于数组中，并且
3. 数字50既存在又重复，解决方案不会显示它。

我已经向网站报告了这个问题，我只是想知道，由于这些问题应该是被策划的，在O(n)中是否有解决方案。我最好的猜测是没有，除非你能以某种方式在所有键/值的映射中插入O(1)中的每个重复数字。

Answer 1

代码不能与示例数据集一起工作的原因是您违反了问题中给出的约束之一。输入数组(长度为n)应该只包含从0到n-1的值。50的值太大了(因为列表中有15个元素)。这个约束就是为什么将n添加到现有值中不会破坏东西的原因。您有一个小于n的原始值(可以用arr[i] % n提取)和一个计数(可以用arr[i] // n提取)。这两个值彼此堆叠在一起，巧妙地重用了现有的数组，而不需要额外的空间。

Answer 2

这个问题可以用dict()来解决。

Python: https://docs.python.org/3.10/library/stdtypes.html#mapping-types-dict

这是一个抽象的数据类型，访问平摊O(1)，正如你所提到的，这正是你所需要的。

Python stdlib也有集合。计数器，它是dict的专门化，它完成了问题要求的90%。

编辑

哦，结果也必须排序。看起来他们想让你使用list()"作为dict"，将整数映射到它们的出现次数，通过它们自己的值作为索引。