来源:
lintcode-排序数组中的单个元素
描述
给定一个排序数组,只包含整数,其中每个元素出现两次,除了一个出现一次的元素。 找到只出现一次的单个元素。...样例
输入:[1,1,2,3,3,4,4,8,8]
输出:2
输入:[3,3,7,7,10,11,11]
输出:10
解题思路
话说这道题在我校招的时候见过的,忘记在面哪个公司时现场问到了....遍历数组,对每个元素进行计数,之后返回只出现一次的元素.
逐个消除....从index=0开始,与之后的每一个元素比较,如果遇到相同的,则将两个元素一起移除掉,如果遍历至结尾,还没有和当前元素相同的,则返回当前元素.
但是今天我不用这两个方法,使用位运算符来解决....出现两次的数字异或之后都为0,拿到0和唯一出现一次的数字异或,结果就是所求的只出现一次的数字.
所以此题的机智的解法就是:对数组中的所有数字异或即可.