首页 > 代码库 > 算法(9)Find the Duplicate Number

算法(9)Find the Duplicate Number

一个数组中的长度是n+1,里面存放的数字大小的范围是【1,n】,根据鸽巢原理,所以里面肯定有重复的数字,现在预定重复的数字就1个,让你找到这个数字!

http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/

使用坐标和数值之间的相互转换!计算机界广为人知的环检测的问题。

网上对这个问题的解释太多了,一搜一大把,环检测方法才是真是的解题之道,环解决方法在上面的链接中有,但是让人茅塞顿开的一个点是在这种解法中是如何合理使用了下标0!!!!还是先分析下这个题目:是说有1到n,n个数字,然后数组的size是n+1的,如果玩过那种动态的拼图游戏,那么0这个位置就是拼图盘上那个永远的空位呀!!!假设一种场景是重复的数字只重复1次,那么我们各个数不断各种转化之后,那么在0这个位置的就是多出来的数字呀!那么攻略中提出来的办法就是找到后面环的入口了!要怎么找呢?!下标从1->n中一定会有环呢?这个是要证明的!这是因为题目中已经说了存在i和j,使得a[i]=a[j]呀,那么怎么保证i和j一定是在这个环上的呢?【这也是该想法跑不到我们脑子里的原因】还是因为题目中的要求太紧了,1->n的数字,散落在0,1->n的空间里,从0开始跳,那么很可能是一下子就跳到了重复元素也可能不是,但是任你怎么坚持到最后,环的入口必然来临,在下面这种场景:

0 1 2 3 4

3 4 1 2 4

a[0] = 3; a[3] = 2; a[2] = 1; a[1] = 4; a[4] = 4;

你侥幸地想着怎么让元素不形成环,但是发现逼到最后,你消耗完了所有的1->n,没办法了,最后一个位置只能从1->n中任选一个填上!

那么就用经典的链表的解决方法来解吧。

环检测的问题:典型场景-->链表

算法(9)Find the Duplicate Number