arrays - 如何使用常量空间在无序数组中查找重复元素

Question

我正在修改试题，我遇到了这个我无法解决的问题 (10.a)。

因为我不能修改数组，我知道我不能使用冒泡排序，但是让我感到困惑的是“不依赖于 n”，这是我唯一能想到的最多是选择 array[i] 元素并将其与 array[i+j] 进行比较，我知道这是不允许的，因为它依赖于 n.

我们的类(class)中有几个人在为我们应该如何处理这个问题而绞尽脑汁，任何人都可以给我们一个关于如何解决它的想法？

对于第二部分，我们还可以，因为我们已经完成了一些可以解决问题的搜索算法。

Answer 1

may use only a constant amount of additional space

这意味着您的算法只允许使用固定数量的内存单元。但是，这并不意味着您不能访问保存输入数组的内存。

请注意，问题是在谈论常数空间，而不是常数时间。

将每个 array[i] 与 array[i+j] 进行比较的解决方案是完全可以接受的，因为它只需要 1 个额外的存储单元(保存结果) .