给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
- show the code:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a = 0
for i in nums:
a ^= i
return a
- 此题可以联想到很多方法，其中有暴力法：两次遍历，寻找只出现过一次的数，复杂度为
- 有哈希法，维护一个字典存储之前出现过的数字，直到找出之前没出现过的数字：即只出现一次的数字。时间和空间复杂度都为
- 但是题目要求线性时间复杂度而且不使用额外空间，所以以上两种方法都不能AC，答案有一种位运算的方法，即异或
^，此符号表示两个数字二进制每位数相同的则为0，不同则为1，所以马上推出两个相同的数字异或的结果是0，0与任何数字异或的结果都是那个数字自身，所以我们只需要遍历一遍即可得出结果。非常简单，也非常牛逼。
网友评论