程序竞赛解答（图）

constant

一个长为n的数组，里面的数为1到n-1的整数。找出一个重复的值。

有一个条件：能够用的存储单元有限制：存在一个与n无关的c，使用的存储单元不超过c*log(n)。例如n是64位整数时，使用的存储单元不能超过8c bytes，即最多存c个64位整数。（数组是 read only 的。可用内存是指数组以外能存能取的部分。）www.ddhw.com

还有一个条件：程序的速度要求是 O(n)。

 www.ddhw.com

设此数组为A。数组A的一个特点是每个值都是数组的指标，也就是可以对数组进行迭代：A[n],A[A[n]],...。这样迭代一定会产生重复，如下图，重复产生在圆和直线相交的地方(J)。我们设计一个找到这一点的方法。

 www.ddhw.com

 www.ddhw.com

设直线的长度为A，圆周长为B。设有两个人从直线的一头(O)开始前进，第一个人的速度是第二个人的两倍。当第二个人到达交点J时，第一个人在圆周上一点X，X到起点的距离满足 X = 2A mod B。 第二个人到达Y点时第一个人追上他。易见Y到J和J到X的距离相等，都是 A mod B。这时再假设有第三个人从起点O出发，速度和第二个人相同，则他们同时到达J点。

 www.ddhw.com

具体程序如下：

 

x = A[n];www.ddhw.com

y = A[A[n]];

while (x != y) {www.ddhw.com

            x = A[x];

            y = A[A[y]];www.ddhw.com

}

 

y = n;www.ddhw.com

while (x != y) {

            x = A[x];www.ddhw.com

            y = A[y];

}

 

www.ddhw.com

 

sean9991

The complexity of within each while loop is O(n).  The while loop could run O(n) times for the x=y condition to be true.  So the worst case complexity of this approach is O(n^2).   I think the simplest approach is to just sum up all the numbers in the array and compare it with n*(n-1)/2.  The storage for n^2 is 2*log(n).  So the storage limit is not the problem, and the complexity is obviously O(n). www.ddhw.com

constant

1) There are two while loops, neither will need repeat.www.ddhw.com   2) It does not work for this particular problem, as is discussed under the original post. www.ddhw.com