在整数数组中找到一个副本

Question

这是个面试问题。

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

在经历了巨大的挣扎之后，我自豪地想出了O(nlogn)解决方案，它占用了O(1)空间。我的想法是将范围[1,n-1]分成两半，并确定哪一半包含输入数组中更多的元素(我使用的是鸽子孔原理)。该算法递归地继续，直到到达间隔[X,X]，其中X发生两次，这是重复的。

面试官很满意，但后来他告诉我，有一个固定空间的O(n)解。他慷慨地提供了很少的提示(与排列有关的东西？)，但我不知道如何想出这样的解决方案。假设他没有说谎，有人能提供指引吗？我搜索过这个问题，发现这个问题的变体很少(更容易)，但没有找到这个特定的问题。谢谢。

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

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 = last element
2. x = element at position x
3. repeat step 2. n times (in total), this guarantees that we entered the cycle

​

1. 测量周期长度

1. a = last x from above, b = last x from above, counter c = 0
2. a = element at position a, b = elment at position b, b = element at position b, c++ (so we make 2 steps forward with b and 1 step forward in the cycle with a)
3. if a == b the cycle length is c, otherwise continue with step 2.

​

1. 找到周期的入口点

1. x = last element
2. x = element at position x
3. repeat step 2. c times (in total)
4. y = last element
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 = element at position x, y = element at position y
7. repeat steps 5. and 6. until a solution was found.

​

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

上面的例子：

1. X取以下数值:8 7 6 4 1 2 3 1 1 2
2. A取下列数值:2 3 4 1 2 B取以下值:2 4 2 4 2 2 因此，c=4(是的，有5个数字，但c只在进行步骤时才会增加，而不是最初)。
3. X取以下值:8 7 6 4 x 1 2 3 4 Y取以下值： 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 b: 3 6 1 4 2 C=5
3. 找到切入点： x: 5 1 3 4 6 y：\x{e76f} 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提出的解决方案(输入得太慢了！)它需要固定的空间(局部变量)，但除此之外，它只使用原始数组作为存储空间。在最坏的情况下，它应该是O(n)，因为一旦找到重复，进程就会终止。

Answer 3

• 这取决于您(您的应用程序)可以使用哪些工具。目前存在许多框架/库。对于C++标准的实例，您可以使用std::map<>，就像maraca提到的那样。
• 或者，如果您有时间，您可以自己实现二叉树，但是您需要记住，元素的插入与通常的数组是不同的。在这种情况下，您可以在特定情况下尽可能地优化重复搜索。

二叉树扩展参考文献：tree