Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1028518
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类:

2008-10-20 23:04:08

前几天参加一个面试,栽在这道题上。
题目:已知有整数1...N(在一个数组中),其中有一个数字缺失,怎么找出来?
我给出的算法是:把给定数组中的数字加起来得到sum,然后用1...N的和减去sum就可以得到缺失的数字了。
这时,面试官问:“如果N很大,这个方法会不会出问题?”
我回答:“加法可能会溢出。”
之后,面试官给出了正确的方法,用XOR操作而不是加法。
后来,我仔细想了一下。其实用加法也是没有问题的。尽管可能溢出,但是,无论溢出与否,最后都会得到正确的结果。关键在于:在计算机中,整数的加法运算满足交换律和结合律。
阅读(2022) | 评论(4) | 转发(1) |
0

上一篇:人月

下一篇:TL2_x86代码的分析(1)

给主人留下些什么吧!~~

chinaunix网友2009-06-08 17:23:32

面试官说的用XOR是好方法,不需要算两次,求和再减需要预处理 XOR只需要便利数组时顺便把1~N异或进去就行了,加法肯定没有位运算快

chinaunix网友2009-04-26 18:27:46

或许这是一个经典问题,如果N非常大,面试官的回答也不一定正确,可以参考一下《编程珠玑》里的解决方案,qsort,二分查找吧。

chinaunix网友2009-01-23 21:56:10

从效率上说,你的要快多了! Σ(1...n)=(1+n)*n/2; 面试官的可要算2次呢!你的这要算一次。 溢出?__int64够了吧,要还会有溢出,那这么大的内存从哪来? 还是因为钱在谁的手上谁说了算!

nmap2008-10-30 09:54:02

Alex,现在工作定好了吗?