Yukang's Page

Find duplicated Number and Cycle detection

2012-04-11


一个有趣的问题,据说这个题目耗费了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 4 5 3

选择index=5还是可以发现环,如果选取0就发现不了3和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;
}
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章