Chinaunix首页 | 论坛 | 博客
  • 博客访问: 107920
  • 博文数量: 31
  • 博客积分: 691
  • 博客等级: 中士
  • 技术积分: 245
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-16 16:45
文章分类

全部博文(31)

文章存档

2012年(4)

2011年(27)

分类:

2011-05-03 23:19:30

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