Leetcode: Single number
Given a list of integers [1,1,2], there is only one number which is not repeated. The numbers can be in any order. The minimum length of the array is 1. Numbers can be negative or positive. The algorithm should have a time complexity of O(n) and a space complexity should be constant O(1).
Given this information, we can use the properties of a set or a map.
from typing import List, Optional
class Solution:
def singleNumber(self, nums: List[int]) -> int:
s = set()
for n in nums:
if n in s:
s.remove(n)
else:
s.add(n)
return s.pop()
if __name__ == '__main__':
s = Solution().singleNumber
print(s([1,2,1,2,3]), 3)set uses the space O(n/2) which seems to be accepted according to the comments in the question.