arrays - 在整数数组中查找重复项

Question

这是一道面试题。

我得到了 [1,n] 范围内的 n+1 个整数数组。数组的特性是它有k (k>=1)个重复项，每个重复项可以出现两次以上。任务是在尽可能最佳的时间和空间复杂度中找到出现不止一次的数组元素。

经过艰苦奋斗，我自豪地提出了占用O(1) 空间的O(nlogn) 解决方案。我的想法是将范围 [1,n-1] 分成两半，并确定两半中的哪一部分包含更多来自输入数组的元素(我使用的是 Pigeonhole 原理)。算法继续递归，直到到达区间 [X,X]，其中 X 出现两次，即重复。

面试官很满意，但后来他告诉我存在空间恒定的O(n)解。他慷慨地提供了一些提示(与排列有关的东西？)，但我不知道如何提出这样的解决方案。假设他没有撒谎，谁能提供指导方针？我搜索了 SO 并发现了这个问题的几个(更简单的)变体，但不是这个特定的变体。谢谢。

编辑:为了让事情变得更加复杂，面试官提到不应修改输入数组。

Answer 1

1. 取最后一个元素 (x)。

2. 保存位置x(y)的元素。

3. 如果 x == y 你找到了重复项。

4. 用 x 覆盖位置 x。

5. 分配 x = y 并继续第 2 步。

您基本上是在对数组进行排序，这是可能的，因为您知道必须在何处插入元素。 O(1) 额外空间和 O(n) 时间复杂度。你只需要小心索引，为简单起见，我假设这里的第一个索引是 1(而不是 0)，所以我们不必做 +1 或 -1。

编辑:不修改输入数组

该算法基于我们必须找到排列循环的入口点的想法，然后我们还找到了一个重复项(为简单起见，同样是基于 1 的数组):

例子:

2 3 4 1 5 4 6 7 8

条目:8 7 6

排列周期:4 1 2 3

正如我们所见，重复的 (4) 是循环的第一个数字。

1. 找到排列周期

   1. x = 最后一个元素
   2. x = 位置 x 的元素
   3. 重复步骤2. n次(总共)，这保证我们进入循环

2. 测量周期长度

   1. a = 上面的最后一个 x，b = 上面的最后一个 x，计数器 c = 0
   2. a = 位置 a 处的元素，b = 位置 b 处的元素，b = 位置 b 处的元素，c++(因此我们使用 b 前进 2 步，使用 a 在循环中前进 1 步)
   3. 如果 a == b 循环长度为 c，否则继续步骤 2。

3. 寻找循环的入口点

   1. x = 最后一个元素
   2. x = 位置 x 的元素
   3. 重复步骤 2. c 次(总共)
   4. y = 最后一个元素
   5. 如果x == y 那么x是一个解(x做了一个完整的循环，y即将进入循环)
   6. x = 位置 x 的元素，y = 位置 y 的元素
   7. 重复第 5 步和第 6 步，直到找到解决方案。

3 个主要步骤都是 O(n) 和顺序的，因此整体复杂度也是 O(n)，空间复杂度是 O(1)。

上面的例子:

1. x 采用以下值:8 7 6 4 1 2 3 4 1 2

2. a 采用以下值:2 3 4 1 2
   b 取以下值:2 4 2 4 2
   因此 c = 4(是的，有 5 个数字，但 c 仅在进行步骤时增加，而不是最初增加)

3. x 采用以下值:8 7 6 4 | 1 2 3 4
   y 采用以下值: | 8 7 6 4
   x == y == 4 最后，这是一个解决方案!

评论中要求的示例 2:3 1 4 6 1 2 5

1. 进入周期:5 1 3 4 6 2 1 3

2. 测量周期长度:
   答:3 4 6 2 1 3
   b: 3 6 1 4 2 3
   c = 5

3. 寻找切入点:
   x: 5 1 3 4 6 | 2 1
   是: | 5 1
   x == y == 1 是一个解决方案