LeetCode 136 Single Number

LeetCode

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:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

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.

题目大意：

数列中，所有数都出现两次除了一个数，求这一个数

异或解题思路(推荐)：

Easy题

解题步骤：

N/A

注意事项：

1. Python代码：

   def singleNumber(self, nums: List[int]) -> int:
   	res = 0
   	for n in nums:
   		res ^= n
   	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

---

HashMap算法II解题思路：

记录频数，最直观解法

Python代码：

def 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代码：

def singleNumber3(self, nums: List[int]) -> int:
	return 2 * sum(set(nums)) - sum(nums)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)