Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
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 * 104-3 * 104 <= nums[i] <= 3 * 104Source
from collections import defaultdict
def single_number(nums):
"""USE HASH TABLE.
Time complexity O(n)
Space Complexity O(n)
"""
hash_table = defaultdict(int) # !! does not work with a normal dict !!
for i in nums:
hash_table[i] += 1
for i in hash_table:
if hash_table[i] == 1:
return i
def single_number(nums):
"""Using set + sum.
Notice that: 2∗(a+b+c) − (a+a+b+b+c) = c
Time complexity O(n)
Space Complexity O(n)
"""
return 2 * sum(set(nums)) - sum(nums)
nums = [2,2,1]
single_number(nums)
1
nums = [4,1,2,1,2]
single_number(nums)
4
nums = [1]
single_number(nums)
1
Could you implement a solution with a linear runtime complexity and without using extra memory?
def single_number(nums):
"""Using XOR.
Notice that:
a ^ 0 = a
a ^ a = 0
a ^ b ^ a = a ^ a ^ b = 0 ^ b = b
Time complexity O(n)
Space Complexity O(1)
"""
a = 0
for i in nums:
a ^= i
return a
nums = [2,2,1]
single_number(nums)
1
nums = [4,1,2,1,2]
single_number(nums)
4
nums = [1]
single_number(nums)
1