LeetCode热题100-只出现一次的数字

给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。题目要求线性时间复杂度空间复杂度为常量而且规定除了某个元素出现1次外其他均出现2次。首先使用普通解题方法哈希表class Solution: def singleNumber(self, nums: List[int]) - int: if not nums: return -1 res {} for i in range(len(nums)): if nums[i] in res: res[nums[i]] res[nums[i]] 1 continue res[nums[i]] 1 for key, value in res.items(): if value 1: return key上面方法对于空间复杂度不满足要求但是是一种容易想到的方式下面的这种不容易想到就是异或运算。由于其他元素都出现2次所以这些元素异或最终为0再和出现1次的元素异或最后就是出现1次的元素值。异或运算^是二进制运算满足以下 3 条性质是解决「只出现一次数字」的核心自身异或为 0a ^ a 0比如 5^50二进制 101^101000异或 0 为自身a ^ 0 a比如 5^05二进制 101^000101交换律和结合律a ^ b ^ c a ^ (b ^ c) (a ^ b) ^ c顺序不影响结果。class Solution: def singleNumber(self, nums: List[int]) - int: res 0 for num in nums: res ^ num return res