那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

求出不在里面的数来

       题目:有一个链表，里面有99个数字，1-100之间的，不重复。问怎样找到那个不在里面的数。

       我能想到的最直观的方法:得出100个数之和,得出99个数之和,相减就是了.

       当然,也可以这么做:初始化一个临时链表,每个元素是100个数中的一个,然后逐个比较.

       不过我还是喜欢自己的想法多一点,因为使用了数学的原理,不知道还有没有更简单的?

posted on 2006-02-26 19:38 那谁 阅读(1095) 评论(9)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 求出不在里面的数来  回复  更多评论   

我在nokia面试的时候就碰上了这到题
我给出的就是上面说的两种方法
也不知道有没有更好的。。。。
2006-02-28 15:36 | djmiss

# re: 求出不在里面的数来  回复  更多评论   

XD
3 遍历这个LIST...设个变量i并随着遍历递增~然后找到遍历到的NODE与i不相等的那个NODE数就是了...
4(加强-》随机递归算法)用随机数抽取1-100中的一个数对LIST进行划分....然后进行按段进行遍历..这样效率上更高....
而i的设置用新的遍历段开始NODE数...

你的算法需要用O（N）的时间遍历整个LIST...然后再用再用100和数
-99个数之合.....
而我的可以用随机数进行划分...- -总体上更快一些...XD
可能还有更多的方法吧...


2006-08-01 00:00 | 3333

# re: 求出不在里面的数来  回复  更多评论   

题目没看清楚...看成已排序了..
这个LIST是未排序了....所以还要加上的排序过程...
加上排序总体上算起来更慢了...
- -结果还是用数学方法最快...
2006-08-01 07:59 | 3333

# re: 求出不在里面的数来[未登录]  回复  更多评论   

98个数呢？
2007-05-07 08:48 | thinkinnight

# re: 求出不在里面的数来  回复  更多评论   

使用辅助数组a【100】， 初始值均为0；遍历，一般情况，遇到i， 则a【i】=1。
然后遍历a【100】， 如为0， 则打印出下标值。
99个数，98个数都适合~
2009-12-18 16:42 | niao010

# re: 求出不在里面的数来  回复  更多评论   

上边人写的我咋看不懂呢
LZ的求和相减是最简单的办法了
还有我的办法是申请一个int a[100]的数组，把99个数一次填入数组的前99个位置，数组最后一个填0，然后给数组排序，然后遍历判断数组下标跟数组相应位置的值是否相等，不相等的，缺的就是下标那个值，如果全相等，缺的就是100这个值。
2011-01-29 16:00 | 加百

# re: 求出不在里面的数来  回复  更多评论   

嘿嘿。。异或就成了。。。
2011-04-26 14:46 | 小阳

# re: 求出不在里面的数来  回复  更多评论   

遍历一遍就好了，遇到偶数就加，遇到奇数就见7，最终也可以从结果看出是哪个数。
2012-08-01 13:38 | 阿债

# re: 求出不在里面的数来  回复  更多评论   

遇到奇数就减
2012-08-01 13:38 | 阿债

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理