在整数数组中查找重复项

Question

这是一个面试问题.

我得到了一系列n+1来自该范围的整数[1,n].数组的属性是它有k (k>=1)重复,每个副本可以出现两次以上.任务是找到在尽可能最佳的时间和空间复杂度下不止一次出现的数组元素.

在经历了重大的挣扎之后,我自豪地想出了O(nlogn)一个占据O(1)空间的解决方案.我的想法是将范围[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步,在循环中向前迈出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. 测量周期长度:
   a:3 4 6 2 1 3
   b:3 6 1 4 2 3
   c = 5

3. 找到切入点:
   x:5 1 3 4 6 | 2 1
   y:| 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提出的解决方案(输入太慢了!)它有恒定的空间要求(对于局部变量),但除此之外只使用原始数组进行存储.它应该是O(n)最坏的情况,因为只要找到重复,该过程就会终止.