今日面试题:缺失的数字

给定一个无序的整数数组,怎么找到第一个大于0,并且不在此数组的整数。比如[1,2,0] 返回 3, [3,4,-1,1] 返回 2。最好能O(1)空间和O(n)时间。

=========================================================

找数字分析原题数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快的方法,找到x。

分析

乍一看这个题目,不少同学立马给出了答案:异或。但举个例子,就会发现,异或是行不通的,一般的方法是利用异或的的如下特性:

A xor A = 0

A xor 0 = A

但是这个题目中,数字都是奇数个的,直接采用之前类似题目的异或方法,已经不合适了。 除此之外,我们还可能想到如下的方法:

采用hashmap,时间复杂度O(n),空间复杂度O(n)

对数组A进行排序,然后在遍历一次,时间复杂度O(nlogn),空间复杂度O(1)

是否还有一些效果更好的方法呢?这一类的题目,即使简单的异或不能解决,也可以从二进制位、位操作方面去考虑,总之这样的大方向是不会错的。

题目中,如果数组中的元素都是三个三个出现的,那么从二进制表示的角度,每个位上的1加起来,应该可以整除3。如果有一个数x只出现一次,会是什么情况呢?

如果某个特定位上的1加起来,可以被3整除,说明对应x的那位是0,因为如果是1,不可能被3整除

如果某个特定位上的1加起来,不可以被3整除,说明对应x的那位是1

根据上面的描述,我们可以开辟一个大小为32的数组,第0个元素表示,A中所有元素的二进制表示的最低位的和,依次类推。最后,再转换为十进制数即可。这里要说明的是,用一个大小为32的整数数组表示,同样空间是O(1)的。

不过这里申请了一个数组的空间,如果这个是不被允许的呢?请大家开动脑筋,我们会在后续的文章中分享。

【分析完毕】

本文来自微信:待字闺中,2013-09-09发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。