Given an array of integers, every element appearstwiceexcept for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce(lambda x, y : x ^ y, nums)
Other ways:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#////////////////////
# using extra memory
#////////////////////
'''
storeH = {}
for item in nums:
# keep a count of the frequency of each element
if item in storeH:
storeH[item] += 1
else:
storeH[item] = 1
# Now traverse the hash
for (k, v) in storeH.iteritems():
#print k, ' -> ', v
if v == 1:
return k
'''
#////////////////////////////////////
# without using xtra memory
# use XOR. XOR is also commutative
#////////////////////////////////////
result = 0
for item in nums:
result ^= item
return result