137 Single Number II
Given an array of integers, every element appearsthreetimes except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Complexity: O(n) time and space
The Idea: Same as just finding a unique number. The problem is trivial (implemented below) if you don't take into account the fact that every number is referenced 3 times. The constant space solution likely involves some bitwise operation on all the elements.
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
hash_count = {}
for key in nums:
if key in hash_count:
hash_count[key] += 1
else:
hash_count[key] = 1
for key, val in hash_count.items():
if val == 1:
return key
obj = Solution()
print(obj.singleNumber([1]))
Last modified 3yr ago