有一個 queue 類別 FirstUnique 特點是要回傳第一個沒有重複的整數。要完成有這項功能的 FirstUnique 。
這個題目倒是沒有 remove 的功能要實現,所以相當容易解決。
要如何知道重複出現?最快的找法就是使用hash 類的資料型態去記錄。
單獨出現過的放在一個 hashtable 不用set是因為我們要保留序列;重複出現的移到第二個 hashtable,並刪除第一個 hashtable 的鍵。
如此 showFirstUnique() 只需要看第一個 hashtable 的第一個鍵,沒有鍵則是 return -1
class FirstUnique:
def __init__(self, nums: List[int]):
self.memo = Counter(nums)
self.memo2 = defaultdict(int)
for key in list(self.memo.keys()):
if self.memo[key] > 1:
del self.memo[key]
self.memo2[key] += 1
def showFirstUnique(self) -> int:
if self.memo:
for key in self.memo:
return key
else:
return -1
def add(self, value: int) -> None:
if value in self.memo2:
pass
elif value in self.memo:
del self.memo[value]
self.memo2[value] += 1
else:
self.memo[value] = 1