那谁的技术博客
感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……
求出不在里面的数来
题目:有一个链表,里面有99个数字,1-100之间的,不重复。问怎样找到那个不在里面的数。
我能想到的最直观的方法:得出100个数之和,得出99个数之和,相减就是了.
当然,也可以这么做:初始化一个临时链表,每个元素是100个数中的一个,然后逐个比较.
不过我还是喜欢自己的想法多一点,因为使用了数学的原理,不知道还有没有更简单的?
posted on 2006-02-26 19:38
那谁
阅读(1090)
评论(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 |
阿债
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
[算法]如何根据数据的多种属性来查找数据
Btree算法实现代码
二分查找学习札记
把二分查找算法写正确需要注意的地方
在一个有序序列中查找重复/不存在的数
自己实现的memcpy
另类的链表数据结构以及算法
memcached内存管理算法
二分查找算法(迭代和递归版本)
ccache发布0.5版本
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 那谁
导航
C++博客
首页
联系
聚合
管理
<
2006年7月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
公告
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(71)
给我留言
查看公开留言
查看私人留言
随笔分类
(264)
avidya(1)
(rss)
C\C++(21)
(rss)
ccache(8)
(rss)
CGL(5)
(rss)
eventrpc(1)
(rss)
gdb(2)
(rss)
libevent(2)
(rss)
lighttpd(10)
(rss)
linux kernel(7)
(rss)
Linux/Unix(32)
(rss)
memcached(2)
(rss)
mktags(4)
(rss)
Nginx(5)
(rss)
Perl(3)
(rss)
tokyo cabinet(5)
(rss)
操作系统(1)
(rss)
读书笔记(3)
(rss)
服务器设计(42)
(rss)
脚本语言(1)
(rss)
经验教训(4)
(rss)
其他(10)
(rss)
设计模式(24)
(rss)
算法与数据结构(48)
(rss)
图形学(1)
(rss)
网络编程(22)
(rss)
随笔档案
(210)
2010年8月 (1)
2010年7月 (3)
2010年6月 (2)
2010年5月 (1)
2010年4月 (2)
2010年3月 (1)
2010年1月 (5)
2009年12月 (7)
2009年11月 (3)
2009年10月 (7)
2009年9月 (2)
2009年8月 (2)
2009年7月 (1)
2009年6月 (3)
2009年5月 (2)
2009年4月 (7)
2009年3月 (2)
2009年2月 (2)
2009年1月 (5)
2008年12月 (1)
2008年11月 (2)
2008年10月 (6)
2008年9月 (12)
2008年8月 (11)
2008年7月 (5)
2008年6月 (2)
2008年4月 (3)
2008年3月 (3)
2008年2月 (1)
2008年1月 (1)
2007年12月 (3)
2007年11月 (3)
2007年8月 (1)
2007年7月 (2)
2007年6月 (2)
2007年5月 (9)
2007年4月 (1)
2007年3月 (8)
2007年2月 (3)
2007年1月 (5)
2006年12月 (4)
2006年11月 (3)
2006年10月 (5)
2006年9月 (4)
2006年8月 (13)
2006年7月 (28)
2006年4月 (1)
2006年3月 (4)
2006年2月 (4)
2006年1月 (1)
2005年12月 (1)
相册
ccache
lighttpd
tokyo cabinet
文件
关于我
我的google reader share
我的google reader share
开源项目
libevent
lighttpd
memcached
PCRE for Windows (Win32)
sqlite
STLFilt
论坛
ChinaUnix
OldLinux
朋友
cugb_cat
Edengundam
win_hate
ypxing
老罗
搜索
最新评论
1. re: memcached采用的网络模型
很好的文章,值得分享。
--纽约网站设计
2. re: 常见设计模式的解析和实现(C++)文档及源码打包下载
评论内容较长,点击标题查看
--残阳丛林
3. re: libevent事件处理框架分析
@hailong
拿走后,堆的恢复是logn
--jiao
4. re: 从半同步-半异步模式谈服务器的设计
学习服务器的一些代码模式。
--王小亮
5. re: 让libevent支持多线程
刚开始以为有个新的方法可以实现多线程。。。。其实就试类似pipe的方式, memcache就是这样做的,可以参考一下
--fly2010love
阅读排行榜
1. 同步/异步与阻塞/非阻塞的区别(53010)
2. libevent事件处理框架分析(45059)
3. epoll学习笔记(41066)
4. 解读google C++ code style谈对C++的理解(38068)
5. 集成libevent,google protobuf的RPC框架(27360)
6. 常见设计模式的解析和实现(C++)文档及源码打包下载(23980)
7. 让libevent支持多线程(23529)
8. 一个关于临时对象和虚拟析构函数的问题(22295)
9. 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)(20215)
10. epoll为什么这么快(20181)
11. Callback在C\C++中的实现(19973)
12. 二分查找算法(迭代和递归版本)(18272)
13. 谈目前项目组的代码提交制度(17807)
14. Linux下面的线程锁,条件变量以及信号量的使用(15640)
15. C++的流设计很糟糕(14581)
16. 二分查找学习札记(14244)
17. memcached采用的网络模型(13888)
18. 红黑树的实现源码(第二次修订版)(13628)
19. 多进程服务器中,epoll的创建应该在创建子进程之后(12651)
20. 第一个socket程序-C\S模式的文件传输程序(12200)
21. 使用tolua++创建基于C\C++语言的lua脚本(12002)
22. 博客迁移(11555)
23. 从半同步-半异步模式谈服务器的设计(11550)
24. Lighty与Nginx的比较分析(11500)
25. Btree算法实现代码(11480)
26. 向德国人低头(11396)
27. epoll相关资料整理(11242)
28. 把二分查找算法写正确需要注意的地方(11101)
29. 程序设计经验总结(10181)
30. 我的项目Makefile文件模板(10137)
31. 带超时机制的DNS解析API(9484)
32. 方法与工具(9332)
33. 自己设想的一个IM服务器的架构(9161)
评论排行榜
1. 常见设计模式的解析和实现(C++)文档及源码打包下载(90)