Find duplicated Number and Cycle detection
四月 11th, 2012一个有趣的问题，据说这个题目耗费了Don Knuth 24小时解决。一起来看看。
# "You are given an array of integers of length n, where each element ranges # from 0 to n - 2, inclusive. Prove that at least one duplicate element must # exist, and give an O(n)-time, O(1)-space algorithm for finding some # duplicated element. You must not modify the array elements during this # process."
这有几个重要的约束，O(n)，O(1)的复杂度，不能修改这个数组。可能有多个数重复了，但至少有一个数重复了。
首先第一个证明问题，等价于n个鸽子，n-1个笼子，那么至少有一个笼子里面有2个鸽子，就是鸽笼原理(抽屉原理), 反证法可以证明。
难的是第二个问题，假设a[0, n], 值都在0,1, …, n-2 范围内。如果扫描这个数组，重复的会出现第二次(废话,囧)，
关键是只能用O(1)的空间，否则用空间记录出现过的就行了。如果把数组看成一个映射，i -> f(i) = a[i]， 那么这个问题可以转换成更抽象的模型。 举个例子：
n = 6 index: 0 1 2 3 4 5 value: 1 4 0 0 3 2
其index对应value映射为为0->1, 1->4, 2->0等等，那么把这个图画出来就是这样：
这个问题转换为求图中环开始的点，因为出现环说明某个点重复出现了。从5开始遍历这个图会在0处发现环，为什么选取5，因为5肯定为一个起点，并且不在0~N-2内。其实只要选取不孤立的那个点当作起点就可以检测环，极端情况比如：
n = 6 index: 0 1 2 3 4 5 value: 0 1 2 3 4 4
选择index=5还是可以发现环，如果选取0就发现不了4和5之间的那个环。
[Cycle detection]是一个经典的计算机问题。经典的算法是Floyd’s cycle-finding algorithm，这个算法简单而优美。严格的数学证明当然可以，也能更明显的从现实经验得出结论。如果一个赛道中间出现某个环(分两种情况，赛道本身是环、赛道前面有一段没环而中间出现一个环9字形)，求这个环的周长C。让两位运动员同时出发，并且P1的速度是P2的两倍，当他们第一重新相遇的时候，一定是在环的某个点上，并且其路程之差为这个环的周长的K倍(K>=1)，这解决了一部分问题，我们知道了KC的值，如果K==1，则得出结果，说明两人刚好是在环开始点相遇。否则就是在环内其余点相遇，可以得知现在P2的路程为KC(P1的路程为2KC), 如果让P3以和P2同样的速度从起点开始，P2继续从相遇点开始跑，那么P2和P3肯定还会相遇，并且相遇的点一定为环开始点! 回到这个问题，这个index的值就是重复的值。代码描述如下：
int detectCycle(int* seq， int Num) { int slow = Num -1; int fast = Num -1; while(1) { slow = seq[slow]; fast = seq[seq[fast]]; if(slow == fast) break; } int finder = Num - 1; while(1) { slow = seq[slow]; finder = seq[finder]; if(slow == finder) break; } return finder; }
算法描述很简单，但其中思维的却很有乐趣。以前同样有一个问题，检测一个链表是否有环，这是由此出来的一个特例，因为对于一个链表的每个节点除了头节点都有一个前节点和后节点(无环则末节点指向空)，而图是一个更通用的模型。
int list_has_cycle(NODE *list) { NODE *fast=list; while(1) { if(!(fast=fast->next)) return 0; if(fast==list) return 1; if(!(fast=fast->next)) return 0; if(fast==list) return 1; list=list->next; } return 0; }
