难度: Medium
Submission
运行时间: 166 ms
内存: 56.5 MB
class FirstUnique:
def __init__(self, nums: List[int]):
self.dup = {}
self.idx = 0
self.list = []
for n in nums:
if n not in self.dup:
self.list.append(n)
self.dup[n] = False
else:
self.dup[n] = True
def showFirstUnique(self) -> int:
while self.idx < len(self.list) and self.dup[self.list[self.idx]]:
self.idx += 1
return self.list[self.idx] if self.idx < len(self.list) else -1
def add(self, value: int) -> None:
if value not in self.dup:
self.list.append(value)
self.dup[value] = False
else:
self.dup[value] = True
# Your FirstUnique object will be instantiated and called as such:
# obj = FirstUnique(nums)
# param_1 = obj.showFirstUnique()
# obj.add(value)
Explain
这个解法使用了一个字典 `dup` 和一个列表 `list` 来管理元素。字典用于跟踪每个元素是否重复出现，如果元素在列表中首次出现，则将其存入列表并在字典中标记为 `False` 表示未重复，若元素再次出现，则在字典中更新该元素为 `True` 表示已重复。方法 `showFirstUnique` 通过遍历列表从当前索引 `idx` 开始查找第一个字典中标记为 `False` 的元素，如果找到则返回该元素，否则返回 `-1` 表示无唯一元素。`add` 方法用于添加新元素，如果元素首次出现，则加入列表并在字典中标记为 `False`，若已存在则更新字典标记为 `True`。
时间复杂度: O(n)
空间复杂度: O(n)
class FirstUnique:
def __init__(self, nums: List[int]):
self.dup = {} # 字典，用于记录元素是否重复
self.idx = 0 # 初始索引，用于 `showFirstUnique` 方法中查找第一个不重复元素
self.list = [] # 列表，存储从未重复的元素
for n in nums:
if n not in self.dup:
self.list.append(n)
self.dup[n] = False # 标记元素为未重复
else:
self.dup[n] = True # 元素重复，标记为 True
def showFirstUnique(self) -> int:
while self.idx < len(self.list) and self.dup[self.list[self.idx]]:
self.idx += 1 # 跳过重复的元素
return self.list[self.idx] if self.idx < len(self.list) else -1 # 返回第一个不重复的元素或者 -1
def add(self, value: int) -> None:
if value not in self.dup:
self.list.append(value)
self.dup[value] = False # 添加新元素，并标记为未重复
else:
self.dup[value] = True # 已存在的元素，标记为重复
Explore
在初始化过程中，第一个出现的数字会被添加到列表中并在字典中标记为未重复（False）。如果该数字后续再次出现，它的标记会在字典中更新为已重复（True），但它仍然会留在列表中。后续重复出现的该数字不会被添加到列表中，只更新字典中的重复标记。
`idx`索引在跳过已标记为重复的元素后不会重置回较小的值，它会一直增加。这意味着每次调用`showFirstUnique`方法时，它会从上一次检查结束的地方继续，而不是重新开始。这种处理方式可以减少重复检查已知重复的元素，从而提高查询性能，尤其是在处理大数据时。
如果一个元素在之前已被添加到字典并标记为重复，即使它在列表中存在，`add`方法在再次遇到此元素时不会将其再次添加到列表中。它只会更新字典中的重复状态。因此，重复元素不会被再次添加到列表中。
当处理大量重复元素时，该算法的性能可能会受到一定影响。尽管`idx`索引避免了重复检查已知重复的元素，但如果列表中的大部分元素都被标记为重复，`showFirstUnique`方法仍然需要遍历这些元素直到找到非重复的元素或遍历完整个列表。这可能导致较高的时间复杂度，尤其是在元素频繁变为重复的场景中。