题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
来源：力扣（LeetCode）

解题思路

  这个题想要写出来不难，难的是原地解决问题。如果没有限制的话建一个频率表找到频率为1的值就可以了。

class Solution:def singleNumber(self, nums: List[int]) -> int:d={}for i in nums:d[i]=d.get(i,0)+1for i,j in d.items():if j==1:return i

  如果加上限制条件的话，思维不发散是很难想到异或运算的。在leetcode的官方中给出了一个符合条件且空间复杂度为O(n)的方法，就是利用异或运算的性质。

class Solution:def singleNumber(self, nums: List[int]) -> int:temp=0for i in nums:temp^=ireturn temp