在列表中查找多个可能的重复整数中的任何一个

Question

给定的阵列n+1整数,每个范围1来n,发现反复的整数.

在面试时我被问到这个问题.这是我的答案:鸽笼原则说必须重复一遍.我尝试使用二进制搜索方法,所以我在Matlab中做了这个,因为这就是我所知道的:

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

所以我认为其中一个,top或者bot,必须比n/2PhP 更大.取这个范围并重复.

我认为这是一个非常好的解决方案,但面试官有点暗示一个人可以做得更好.请发布您知道的更好的解决方案.

Answer 1

我不确定你是如何定义"更好"的,但也许这有资格.至少它与您的解决方案和链表问题的解决方案(双关语意图)不同.

如果我们走一条路

n+1 --> array[n+1] --> array[array[n+1]] --> ...

那么这条路径包含一个循环,当且仅当array^k[n+1] = array^l[n+1]某些循环k != l,即当且仅当有重复时.现在问题变成了一个常见的链表问题,可以解决如下问题.

在第一个节点上启动两个粒子.让第一个粒子以单位速度移动,让第二个粒子以两倍的单位速度移动.然后,如果有一个循环,第二个粒子将最终循环回到第一个粒子后面,最终它们将是相同的.为什么？好吧,如果你把粒子想象成一个圆圈(它们将在找到环路时它们),每次单位时第二个粒子得到一个直接靠近第一个粒子的步骤.因此他们最终必须相互碰撞.他们一个人,你找到了一个循环.要找到重复的值,只需通过让一个粒子静止而另一个粒子再次运行循环来获得循环的长度.然后在开始时再次启动两个粒子,让一个移动前面的循环长度,然后将两个粒子一起运行,它们之间保持恒定距离,直到它们在循环开始时再次相遇.

由于一些评论员感到愤怒,我没有包括如何在链表中找到循环的所有细节,现在就是.没有承诺这不是错误的(毕竟它是Matlab式的伪代码),但它至少应该解释这个想法.

%% STEP 1: find a point in the cycle of the linked list using a slow and fast particle
slow = n+1;
fast = n+1;
for i=1 to n+1
    slow = array[slow];
    fast = array[array[fast]];
    if (slow == fast)
        break;
end

%% STEP 2: find the length of the cycle by holding one particle fixed
length = 1;
fast = array[fast]
while fast != slow
    fast = array[fast];
    length = length+1;
end

%% STEP 3: find the repeated element by maintaining constant distance between particles
slow = n+1;
fast = n+1;
for i=1 to length
    fast = array[fast];
end
while fast != slow
    fast = array[fast];
    slow = array[slow];
end

%% STEP 4: return the repeated entry
return slow;

在这里我开始n+1因为array[i]介于1和n之间,所以这两个粒子都不会被送回n+1.这使得最多一次通过数组(虽然不按顺序)并跟踪两个粒子(慢和快)和一个整数(长度).因此空间为O(1),时间为O(n).