Given an array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
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 .\n
We use hash table to avoid the time required for searching the elements.\n
popitemto get it
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 .\n
Time complexity : .
sum will call
next to iterate through .\nWe 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
So we can XOR all bits together to find the unique number.\n\n
Time complexity : . We only iterate through , so the time complexity is the number of elements in .\n
Space complexity : .\n
Analysis written by: @Ambition_Wang\n