LC 1429 [M] First Unique Number - ALawliet/algorithms GitHub Wiki
doubly-linked list + hashmap
class DLL:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
class FirstUnique:
def __init__(self, nums: List[int]):
self.map = {}
self.head = DLL('#')
self.cur = self.head
for n in nums:
self.add(n)
def showFirstUnique(self) -> int:
# maintain first element is always unique
return self.head.next.val if self.head.next else -1
def add(self, value: int) -> None:
if value not in self.map:
node = DLL(value)
self.map[value] = node
self.cur.next = node
node.prev = self.cur
self.cur = self.cur.next
else:
# if it already exists/is repeated, then remove it
node = self.map[value]
if node == self.cur:
self.cur = self.cur.prev
if node.next:
node.next.prev = node.prev
if node.prev:
node.prev.next = node.next
node.next = None
node.prev = None
# Your FirstUnique object will be instantiated and called as such:
# obj = FirstUnique(nums)
# param_1 = obj.showFirstUnique()
# obj.add(value)
deque + counter
class FirstUnique:
def __init__(self, nums):
self.deque = deque(nums)
self.count = Counter(nums)
def showFirstUnique(self):
while self.deque:
x = self.deque.popleft()
if self.count[x] == 1:
self.deque.appendleft(x)
return x
return -1
def add(self, value):
self.deque.append(value)
self.count[value] += 1