一个计算机查找的问题,100分送上,有加分100

来源:百度知道 编辑:UC知道 时间:2024/05/22 03:32:51
有1百万个非负的整数的数组,
这些数不重复,也没有按照顺序排列
储存在一个电脑文件里面,
我想往里面存入一个非负的整数,
问有什么方法能最快判定这个数不重复?
实际上就想当于在这些数里面加入一个不重复的数,怎么加。。我加入一个数,怎么判断它是否在这100万个数里面
就是说一个原理就可以了,大概怎么做,不用实际的程序,我把200分都送上
一个个的比当然可以
问题是这样比较慢。。。有没有快的方法

你的数都没排序,线性遍历已经是最快的了,如果发现有重复就不插入,遍历到底都没重复就插入。否则只有一种办法,第一次插入的时候先排序,然后再遵照排序的规则往里面插入你要插入的数(就是说你完成插入之后不能破坏了那种序),这就有很多算法了,比如你把所有的数按递增或递减排序,然后你的插入就可以按照二分法插入,这种插入的算法复杂度是log(n),其中log以2为底,n是你的数组的元素个数。另外也可以选择建立一棵二叉搜索树,堆排序或者归并排序。但是这些方法都涉及到排序,复杂度也不小,但是一劳永逸的,你第一次完成了排序,后面就只需要插入新的数后仍然维持这个序就可以了,但是序的维护如果算法不当工作量也不会小,甚至还不如线性遍历。所以这个问题本身具有一定的灵活性和多样性。需要针对具体情况做出相应的选择。关于这些排序算法,很多书上都有,或者在网上搜一搜也能搜得到。不过有一点楼主要记住,排序,搜索,插入三者可以说是牵一发动全身的关系,而牵着这一发的正是排序。排序工作做好了,搜索和插入一般情形下相对没排序时效率都会有所提升。而且这三者经常相伴出现,所以不要只想到提高其中一个的效率,而应该同时兼顾三者,考察它们配合时的整体效率!

原先的想法是错误的。。刚要提交回答才想到这个想法有问题,原来的想法在下面,可以稍微看下。因为冒泡排序要进行比较的,如果进行比较还不如直接跟原数比较。。由于这些数没有排序。我个人认为要快速算法肯定是要执行遍历的,也就是一个个比较过去。。提高只能提高在快速得到比较结果上,也就是提高比较算法的速度。

对比较算法的建议
比较2个数字大小,如果是java有直接的比较算法,如果不是Java的话,比较方式应该多样点,先比较长度,然后比较个位,十位这样上去,如果一个不相同程序就可以返回继续执行,这个是个小建议。。

/*下面是原先错误的想法*/
我个人的想法是这个的
编个程序,这个程序声明一个500长度的数组,每次从你的文件中读入500个数字,然后进行排序,如果是JAVA的话可以直接调用排序方法,其他语言可以使用冒泡之类的算法。排序后要查找就比较容易了,使用2分法相信你应该会吧。
这样500个数组一次要执行2000次。最坏情况大概要一个小时吧,这个效率跟机子快慢有关系。。
/