<div>
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
<pre>Input: nums = [2,2,1] Output: 1 </pre>
Example 2:
<pre>Input: nums = [4,1,2,1,2] Output: 4 </pre>
Example 3:
<pre>Input: nums = [1] Output: 1 </pre>
Constraints:
1 <= nums.length <= 3 * 10<sup>4</sup>-3 * 10<sup>4</sup> <= nums[i] <= 3 * 10<sup>4</sup>- Each element in the array appears twice except for one element which appears only once.
</div>
题目大意：
数列中，所有数都出现两次除了一个数，求这一个数
异或解题思路(推荐)：
Easy题
解题步骤：
N/A
注意事项：
Python代码：
1
2
3
4
5def singleNumber(self, nums: List[int]) -> int:
res = 0
for n in nums:
res ^= n
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
HashMap算法II解题思路：
记录频数，最直观解法
Python代码：
1
2
3def singleNumber2(self, nums: List[int]) -> int:
num_to_count = collections.Counter(nums)
return [n for n, count in num_to_count.items() if count == 1][0]
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
Math算法III解题思路：
用set求单一元素和乘以2减去原数组的和
Python代码：
1
2def singleNumber3(self, nums: List[int]) -> int:
return 2 * sum(set(nums)) - sum(nums)
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
