First Unique Number

https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/531/week-4/3313/

LRU 解法 照搬 Double LinkedList & HashMap 模板

class Node:
    def __init__(self,val):
        self.val = val
        self.prev = None
        self.next = None
        
class FirstUnique:

    def __init__(self, nums: List[int]):
        self.d = dict()
        self.cnt = 0
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        for num in nums:
            self.add(num)
        

    def showFirstUnique(self) -> int:
        curr = self.head.next
        if self.cnt == 0:
            return -1
        return curr.val
        

    def add(self, value: int) -> None:
        newNode = Node(value)
        if value not in self.d:
            self.d[value] = newNode
            prev = self.tail.prev
            prev.next = newNode
            newNode.prev = prev
            newNode.next = self.tail
            self.tail.prev = newNode
            self.cnt+=1
        else:
            if self.d[value] != -1:
                self.__remove(self.d[value])
                self.d[value] = -1
                self.cnt-=1
    
    def __remove(self,node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

简化解法因为 Python OrderDict 本质就是 Double LinkedList & HashMap

from collections import OrderedDict
class FirstUnique:

    def __init__(self, nums: List[int]):
        self.d = OrderedDict()
        self.s = set()
        for num in nums:
            self.add(num)

    def showFirstUnique(self) -> int:
        #print(self.d)
        if len(self.d) == 0:
            return -1
        return next(iter(self.d))
        

    def add(self, value: int) -> None:
        if value not in self.s:
            self.s.add(value)
            self.d[value] = 1
        else:
            if value in self.d:
                self.d.pop(value)

这里 next(iter(self.d)) 返回OrderDict第一个key