一个长为n的数组，里面的数为1到n-1的整数。找出一个重复的值。
有一个条件：能够用的存储单元有限制：存在一个与n无关的c，使用的存储单元不超过c*log(n)。例如n是64位整数时，使用的存储单元不能超过8c bytes，即最多存c个64位整数。（数组是 read only 的。可用内存是指数组以外能存能取的部分。）
还有一个条件：程序的速度要求是 O(n)。
设此数组为A。数组A的一个特点是每个值都是数组的指标，也就是可以对数组进行迭代：A[n],A[A[n]],...。这样迭代一定会产生重复，如下图，重复产生在圆和直线相交的地方(J)。我们设计一个找到这一点的方法。
设直线的长度为A，圆周长为B。设有两个人从直线的一头(O)开始前进，第一个人的速度是第二个人的两倍。当第二个人到达交点J时，第一个人在圆周上一点X，X到起点的距离满足 X = 2A mod B。 第二个人到达Y点时第一个人追上他。易见Y到J和J到X的距离相等，都是 A mod B。这时再假设有第三个人从起点O出发，速度和第二个人相同，则他们同时到达J点。
具体程序如下：
x = A[n];
y = A[A[n]];
while (x != y) {
x = A[x];
y = A[A[y]];
}
y = n;
while (x != y) {
x = A[x];
y = A[y];
}
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). |
1) There are two while loops, neither will need repeat. 2) It does not work for this particular problem, as is discussed under the original post. |
| 欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |