题目要求
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
(LeetCode136也就是这么个题吧,简单题,要求是最好写出线性的时间复杂度和O(1)的空间复杂度)
分析首先很容易想的就是开一个数组计数,但算法效率肯定不好。 还可能用哈希什么的去做,线性的空间能保证吗? …… 其实这问题本质上是考察 按位异或 的位运算符的。
怎么说? 学过离散数学我们知道,异或是说,同则取0,异则取1。 按位异或就是按照二进制的表示,两个数每一位同则取0,异则取1。 异或也有交换律:a ^ b = b ^ a
,所以顺序无所谓的。 既然其他数都是出现两次,那我们就可以认为遍历结束后的时候,每个两两相同的数值对异或后都是0了,剩下的是那个落单的。 怎么让结果就是落单的呢? 还得从0身上下手: a ^ 0 = a
所以说,只要初值设成0的话,遍历一趟数组,逐一异或,最终结果就是出现一次的数。
class Solution {
public int singleNumber(int[] nums) {
int n = 0;
for (int i : nums) {
n ^= i;
}
return n;
}
}