Solution 1
class Solution:
def singleNumber(self, nums: List[int]) -> int:
#Use Exclusive or
#a XOR 0 = a
#a XOR a = a
#a XOR b XOR a = a XOR a XOR b = b
res = 0
for num in nums:
res ^= num
return res
Time complexity is O(n). Space complexity is O(1).
Solution 2
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = []
for num in nums:
if num in res:
res.remove(num)
else:
res.append(num)
return res.pop() #retur an int, not a list
Time complexity is O(n*n). Iterating through nums takes O(n) time * search num in the list takes O(n) time. Space complexity is O(n). n is the size of the list.
Solution 3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
dic = {}
for num in nums:
if num in hash_table:
dic.pop(num)
else:
dic[num] = 0
return hash_table.popitem()[0] #retur an int, not a list
#pop(): Removes and returns an element from a dictionary having the given key.
#popitem():Removes the arbitrary key-value pair from the dictionary and returns it as tuple.
Time complexity is O(n). Iterating through nums takes O(n) time * search num in the dictionary takes O(1) time. Space complexity is O(n). n is the size of the nums.
Solution 4
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return 2 * sum(set(nums)) -sum(nums) #set() is used for creating sets
Time complexity is O(n). O(n+n)=O(n). Space complexity is O(n).
步步发财 