Chinaunix首页 | 论坛 | 博客
  • 博客访问: 310847
  • 博文数量: 135
  • 博客积分: 1860
  • 博客等级: 上尉
  • 技术积分: 1440
  • 用 户 组: 普通用户
  • 注册时间: 2008-01-05 20:39
文章分类
文章存档

2012年(2)

2011年(130)

2009年(2)

2008年(1)

我的朋友

分类:

2011-08-23 13:19:59

前几天下班途中跟同事聊到了一道面试题,大意是,给你1-1000个连续自然数,然后从中随机去掉两个,再打乱顺序,要求只遍历一次,求出被去掉的两个数。

这题其实挺为面试者的,因为要求1分钟内说出解法,且不能使用计算机、纸和笔。如果之前没有遇到过类似的题目,加上面试时的紧张心情,很难能在那么短的时间里想到解决方案,至少我做不到。

好在我有时间,上网看了一下,比较常见的有两种方法

求方程组的解

遍历被打乱的数组时,计算value的累加值和value平方的累加值。结合未打乱之前的数组,这样就能得出x+y = m与x*x+y*y = n两个方程,解这组方程即可算出被去掉的两个数。这种方法比较容易理解,实现起来也比较简单

使用异或

这个就麻烦点了。先来说说异或的定义:两个二进制位不同的取1。再来说说异或的两个特性:顺序无关 / 对一个数异或两次等于没有异或。顺序无关就是说异或的元素可以随意交换顺序,而不会影响结果。异或两次可以理解为+x和-x。

计算出x^y的值

首先,这两个数组(打乱前和打乱后)各自异或,也就是1^2^…^1000,得到两个异或值。再对这两个异或值进行一次异或,这样就得到了x^y的指(重复部分互相抵消了)。

// 其实就是把数组的所有元素进行异或,重复部分互相抵消
result = 1^2^...^1000^1^2...^1000;
result = 1^1^2^2...^x...^y...^1000^1000;
result = x^y;

获取计算出的异或值的1所在的位置,并继续异或

因为x和y是两个不同的整数,所以这两个数的异或结果,转化为二进制的话,一定在某位是1,假设在第3位。也就是说如果把原始数组按第3位是否为0进行划分,就可以分成两个数组,每个数组各包含一个被抽取的数。如果打乱后的数组也按这个规则划分为两个数组,这样就得到了4个数组,其中两组是第3位为0,另外两组是第3位为1。把第3位为0的两个数组所有元素进行异或就能得到被抽取的一个数,同理也就能获得另外一个被抽取的数,于是问题解决。

阅读(6889) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~