array problem of bit analysis
题目:一个数组里,除了三个数是唯一出现的,其余的都出现偶数个,找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】,只有1,5,6这三个数字是唯一出现的,我们只需要输出1,5,6中的一个就行。
某米的面试题,这是鄙人最喜欢的几个公司之一,和某歌公司有这相似的企业文化,当年google音乐产品经理的洪峰也转去小米,非常佩服这种为祖国事业奋斗的牛人!
这种找数题的思路就是,首选用位运算。当然这一般是优于建个数组数count,或者n^2以上的朴素算法的。
先是所有数疑惑,模仿找唯一出现一次的数的思路,结果是这三个数的异或值。然后如果找到两个数异或值,这两个再异或结果就出来了,但是两个数的异或值想了下,没思路,于是这条路放弃。
然后分析三个数异或真值表,发现奇数个1异或为1,偶数个1异或为0,那么我在想,由于三个数不可能完全相同,甚至不可能有两个相同,于是把结果为0 的 011 101 110 和异或结果为1的 001 100 010这六种情况至少出现
一次,于是方法形成,遍历一遍,遇到0,将该bit为0的全部异或,如果不等于之前n个数异或result,就继续,否则返回,遇到1,将该bit为1的全部异或,同样处理,直到遍历完最多32bit,如果是*86系统的话,
时复O(n), n+32n 空复 O(1)
题目来源:http://blog.csdn.net/wypblog/article/details/8032898#reply