一万个“无序”数查找两个重复数,在O(N)的基础上再快一点-阿里云开发者社区

开发者社区> 人工智能> 正文

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

简介:

原题见 莫贝特 的博客,意思是 1-1000组成的序列,再加入一个1-1000之间的数,然后将这1001个数打乱顺序。

问题:你现在拿到了这样一组数,请用最少的内存开销、最少的时间开销,找出那个重复的数。

由于最初没看清题意,以为是有序数列,于是想到了二分法。二分法是好方法,但是运用的前提条件搞错了,自然结果也就错了,受到 Zhao 首长的严肃批评。

但是本人对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,如需转载请自行联系原作者



版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章