在整数数组中查找重复项

Question

这是一道面试题。

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

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

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

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

Answer 1

取最后一个元素 (x)。
保存位置x(y)的元素。
如果 x == y 你找到了重复项。
用x覆盖位置x。
赋值 x = y 并继续第 2 步。

您基本上是在对数组进行排序，这是可能的，因为您知道必须在何处插入元素。 O(1) 额外 space 和 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. x = 最后一个元素
2. x = 位置 x 处的元素
3. 重复第2步n次（总共），保证进入循环
测量周期长度
1. a = 上面的最后一个 x，b = 上面的最后一个 x，计数器 c = 0
2. a = 位置 a 的元素，b = 位置 b 的元素，b = 位置 b 的元素，c++（所以我们用 b 前进 2 步，在循环中用 a 前进 1 步）
3. 如果a == b循环长度为c，否则继续步骤2。
寻找循环的入口点
1. x = 最后一个元素
2. x = 位置 x 处的元素
3. 重复步骤 2. c 次（总共）
4. y = 最后一个元素
5. if x == y then x is a solution (x made one full cycle and y is just about to enter the cycle)
6. x = 位置 x 处的元素，y = 位置 y 处的元素
7. 重复第 5 步和第 6 步，直到找到解决方案。

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

上面的例子：

x 取以下值：8 7 6 4 1 2 3 4 1 2
a 采用以下值：2 3 4 1 2
b 采用以下值：2 4 2 4 2
因此 c = 4（是的，有 5 个数字，但 c 仅在进行步骤时增加，而不是最初增加）
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

进入周期：5 1 3 4 6 2 1 3
测量周期长度：
一：3 4 6 2 1 3
b: 3 6 1 4 2 3
c = 5
寻找切入点：
x: 5 1 3 4 6 | 2 1
是： | 5 1
x == y == 1 是解

Answer 2

这是一个可能的实现：

function checkDuplicate(arr) {
  console.log(arr.join(", "));
  let  len = arr.length
      ,pos = 0
      ,done = 0
      ,cur = arr[0]
      ;
  while (done < len) {
    if (pos === cur) {
      cur = arr[++pos];
    } else {
      pos = cur;
      if (arr[pos] === cur) {
        console.log(`> duplicate is ${cur}`);
        return cur;
      }
      cur = arr[pos];
    }
    done++;
  }
  console.log("> no duplicate");
  return -1;
}

for (t of [
     [0, 1, 2, 3]
    ,[0, 1, 2, 1]
    ,[1, 0, 2, 3]
    ,[1, 1, 0, 2, 4]
  ]) checkDuplicate(t);

它基本上是@maraca 提出的解决方案（打字太慢了！）它有常量 space 要求（对于局部变量），但除此之外只使用原始数组进行存储。在最坏的情况下应该是O(n)，因为一旦发现重复，进程就会终止。

Answer 3

这取决于你（你的应用程序）可以使用什么工具。目前有很多 frameworks/libraries 存在。例如，在 C++ 标准的情况下，您可以使用 std::map<> ，如 maraca 所述。
或者如果你有时间你可以自己实现二叉树，但你需要记住元素的插入与普通数组的比较不同。在这种情况下，您可以根据您的特定情况尽可能优化重复项搜索。

二叉树解释。参考： https://www.wikiwand.com/en/Binary_tree

Answer 4

如果允许 non-destructively 修改输入向量，那么这很容易。假设我们可以 "flag" 通过取反输入中的一个元素（这显然是可逆的）。在这种情况下，我们可以进行如下处理：

注意：下面假设向量从1开始索引。由于它可能从0开始索引（在大多数语言中），你可以用[=40实现"Flag item at index i" =].

将 i 设置为 0 并执行以下循环：
1. 递增 i 直到项目 i 未标记。
2. 将 j 设置为 i 并执行以下循环：
  1. 将 j 设置为矢量[j]。
  2. 如果 j 处的项目被标记，则 j 是重复项。终止两个循环。
  3. 在 j 标记项目。
  4. 如果j != i，继续内循环。
遍历向量，将每个元素设置为其绝对值（即取消标记所有内容以恢复向量）。

在整数数组中查找重复项

Find a duplicate in array of integers

arrays

algorithm

big-o

time-complexity

space-complexity