Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Algorithm
Python
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ no_duplicate_list = [] for i in nums: if i not in no_duplicate_list: no_duplicate_list.append(i) else: no_duplicate_list.remove(i) return no_duplicate_list.pop()
Complexity Analysis
Time complexity : . We iterate through , taking time. We search the whole list to find whether there is duplicate number, taking time. Because search is in the for
loop, so we have to multiply both time complexities which is .
Space complexity : . We need a list of size to contain elements in .
Algorithm
We use hash table to avoid the time required for searching the elements.
pop
popitem
to get itPython
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ hash_table = {} for i in nums: try: hash_table.pop(i) except: hash_table[i] = 1 return hash_table.popitem()[0]
Complexity Analysis
Time complexity : . Time complexity of for
loop is . Time complexity of hash table(dictionary in python) operation pop
is .
Space complexity : . The space required by is equal to the number of elements in .
Concept
Python
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ return 2 * sum(set(nums)) - sum(nums)
Complexity Analysis
Time complexity : . sum
will call next
to iterate through .
We can see it as sum(list(i, for i in nums))
which means the time complexity is because of the number of elements() in .
Space complexity : . set
needs space for the elements in nums
Concept
So we can XOR all bits together to find the unique number.
Python
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ a = 0 for i in nums: a ^= i return a
Complexity Analysis
Time complexity : . We only iterate through , so the time complexity is the number of elements in .
Space complexity : .
Analysis written by: @Ambition_Wang