一万个“无序”数查找两个重复数，在O(N)的基础上再快一点

 目前的算法是：（1001个数字的和）- （1000个数字的和）=  （1001个数字的和）- n*（n+1）/2=  重复数字，求和需要1000次循环。
这个算法之所以能成立，是因为序列是由1-1000的连续数字组成的，因此，不管他们怎么排列，（1000个数字的和）都是从1加到1000。但是，如果这1000个数字不是连续的，比如是从1-100000中随机选出来的互不相同的1000个数，那么这个算法就不成立了，因为我们无法知道（1000个数字的和）到底是哪1000个数字。

既然现在给出的条件是1-1000的乱序，那么就可以利用连续这一特殊性来改进算法。

最简单的方法应该是：再开辟一个1000空间的数组 list2 ，将这1001个数字从第一个开始，依次放到 list2 中他的编号位置上
比如：
list2[list[0]-1]=list[0]
list2[list[1]-1]=list[1]
依次这样做下去，直到某个要保存的数字在 list2 对应的位置上已经存在，就找到了这个数字。
但是这次我看清要求了，不能开辟新的空间。

虽然不能开辟新的空间，思路却已经有了，就是利用连续性和索引的对应关系，具体算法描述如下：
1、取出第一个位置的数字：p1=list[0]
2、将第一个位置标记：list[0]=0
3、取出 p1 位置的数字：p2=list[p1]
4、将 p1 位置标记：list[p1]=0
5、取出 p2 位置的数字：p3=list[p2]
6、将 p2 位置标记：list[p2]=0
.............
依次做下去，直到下一个要找的位置被标记过了，数字就找到了。
原因是：那个重复的数字，最终要访问他自己的位置第二次，当他访问时，发现位置已经被上一个自己访问过了，他就知道自己不是唯一的了。

这种算法叫什么名字我也不知道，能不能叫漫游算法？
在最好的情况下，他的循环次数是 1，比如[1,1,....1000]
在最坏的情况下，他的循环次数是 1000，比如[1,2,3......1000,1000]
平均情况下，他的循环次数是 N/2，虽说数量级上仍然是 O(N)级别的，但是平均来说，仍然比前面的求和法快了一倍

下面给出代码，还是可爱的 Python ：

# !/usr/bin/python
#  -*- coding: GBK -*-

import  random

#  生成数列
arr_length = 10001
list = range( 1 ,arr_length)

# 加入一个随机数
rnd = random.randrange( 1 ,arr_length)
list.append(rnd)
print   ' \n重复数为： ' +  str(rnd)

# 打乱顺序
random.shuffle(list)

#  正式开始查找算法 
count = 0
idx = 0  
while  (list[idx] != 0):
    count = count  + 1
    temp = list[idx] 
    list[idx] = 0
    idx = temp
    
print   " 找到：%d，循环 %d 次 "   %  (temp,count)

多次运算结果如下图：
 

//==========================================

本文转自左洸博客园博客，原文链接：http://www.cnblogs.com/myqiao/archive/2009/07/22/1528271.html，如需转载请自行联系原作者