LeetCode「First Unique Number」题解从 O(N²) 暴力到 O(1) 的「队列 哈希表」三阶演进【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库文档 articles/first-unique-number.md 为骨架完整梳理「First Unique Number」这道数据结构设计题的三套解法覆盖 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言实现。读完你将掌握「队列保序 哈希表判重」的经典组合理解惰性删除lazy removal与主动删除eager removal两种维护策略的差异以及它们在add/showFirstUnique高频调用场景下的复杂度含义并能直接迁移到 LRU Cache 等同类「保序 判重」设计题中。一、问题定义一个需要持续维护全局首个唯一元素的数据结构这道题要求设计一个名为FirstUnique的类其核心是在不断有数据流入的前提下随时回答当前所有已见元素中第一个只出现过一次的元素是谁。标准接口包含三个方法方法语义FirstUnique(nums)构造函数接收一个初始整数数组将其全部纳入数据结构showFirstUnique()返回当前流中第一个只出现一次的元素若不存在这样的元素返回-1add(value)向数据流中追加一个新值追加后可能使某个元素从唯一变为不唯一举例来说若初始数组为[2, 3, 5]则showFirstUnique() - 2 # 2、3、5 都只出现一次最早出现的唯一元素是 2 add(5) # 5 出现第二次不再是唯一元素 showFirstUnique() - 2 # 2、3 仍唯一2 依然最靠前 add(2) # 2 出现第二次不再是唯一元素 showFirstUnique() - 3 # 只剩 3 唯一 add(3) # 3 出现第二次没有任何唯一元素了 showFirstUnique() - -1注意showFirstUnique()是只读查询不应该把队首元素真正移出数据结构——文档源码注释中特别强调 We dont want to actuallyremovethe valuearticles/first-unique-number.md。这与队列的经典peek语义一致。它的难点在于唯一性状态是动态变化的——一个元素在第二次出现时就从唯一降级为不唯一且这种降级会发生在任意位置不一定在队首。因此保序与快速判重必须同时满足这正是本仓库 README.md 中归类为队列Queue与哈希表Hash Map综合题的原因。前置知识三个基础数据结构动手前需要熟悉队列QueueFIFO先进先出结构用于维护元素的插入顺序保证能取到第一个。哈希表Hash Map以 O(1) 时间跟踪每个元素的计数或唯一性状态这是把showFirstUnique()从 O(N) 降到 O(1) 的关键。LinkedHashSet / OrderedDict把哈希表 O(1) 查找与插入顺序保持两者合一让按值删除 取第一个都能高效完成。二、方法一暴力解法Brute Force思路Intuition最直接的想法把所有数字放进一个队列。调用showFirstUnique()时从头到尾扫描队列对每个元素统计它在整个队列中出现的次数返回第一个计数恰好为 1的元素。这个方法正确性毋庸置疑但代价是每次查询都要做一轮完整的扫描与计数复杂度随数据规模急剧增长。算法步骤构造函数将初始数组的所有数字放入队列。add(value)直接把值追加到队列末尾O(1)。showFirstUnique()遍历队列对每个元素统计其在整个队列中的出现次数返回第一个计数为1的元素若全部遍历完仍未找到返回-1。多语言实现class FirstUnique: def __init__(self, nums: List[int]): self._queue deque(nums) def showFirstUnique(self): for item in self._queue: if self._queue.count(item) 1: return item return -1 def add(self, value): self._queue.append(value)class FirstUnique { private QueueInteger queue new ArrayDeque(); public FirstUnique(int[] nums) { for (int num : nums) { queue.add(num); } } public int showFirstUnique() { for (int num : queue) { int count Collections.frequency(queue, num); if (count 1) { return num; } } return -1; } public void add(int value) { queue.add(value); } }class FirstUnique { private: queueint q; public: FirstUnique(vectorint nums) { for (int num : nums) { q.push(num); } } int showFirstUnique() { queueint temp q; while (!temp.empty()) { int num temp.front(); temp.pop(); int count 0; queueint countTemp q; while (!countTemp.empty()) { if (countTemp.front() num) count; countTemp.pop(); } if (count 1) { return num; } } return -1; } void add(int value) { q.push(value); } };class FirstUnique { /** * param {number[]} nums */ constructor(nums) { this._queue nums.slice(); } /** * return {number} */ showFirstUnique() { for (let item of this._queue) { let count 0; for (let el of this._queue) { if (el item) count; } if (count 1) { return item; } } return -1; } /** * param {number} value * return {void} */ add(value) { this._queue.push(value); } }public class FirstUnique { private Queueint queue new Queueint(); public FirstUnique(int[] nums) { foreach (int num in nums) { queue.Enqueue(num); } } public int ShowFirstUnique() { foreach (int num in queue) { int count 0; foreach (int el in queue) { if (el num) count; } if (count 1) { return num; } } return -1; } public void Add(int value) { queue.Enqueue(value); } }type FirstUnique struct { queue []int } func Constructor(nums []int) FirstUnique { queue : make([]int, len(nums)) copy(queue, nums) return FirstUnique{queue: queue} } func (this *FirstUnique) ShowFirstUnique() int { for _, item : range this.queue { count : 0 for _, el : range this.queue { if el item { count } } if count 1 { return item } } return -1 } func (this *FirstUnique) Add(value int) { this.queue append(this.queue, value) }class FirstUnique(nums: IntArray) { private val queue ArrayDequeInt() init { for (num in nums) { queue.addLast(num) } } fun showFirstUnique(): Int { for (num in queue) { var count 0 for (el in queue) { if (el num) count } if (count 1) { return num } } return -1 } fun add(value: Int) { queue.addLast(value) } }class FirstUnique { private var queue: [Int] init(_ nums: [Int]) { queue nums } func showFirstUnique() - Int { for item in queue { var count 0 for el in queue { if el item { count 1 } } if count 1 { return item } } return -1 } func add(_ value: Int) { queue.append(value) } }struct FirstUnique { queue: VecDequei32, } impl FirstUnique { fn new(nums: Veci32) - Self { let queue: VecDequei32 nums.into_iter().collect(); FirstUnique { queue } } fn show_first_unique(self) - i32 { for item in self.queue { let count self.queue.iter().filter(|x| x item).count(); if count 1 { return item; } } -1 } fn add(mut self, value: i32) { self.queue.push_back(value); } }复杂度分析时间复杂度构造函数$O(K)$仅入队add()$O(1)$队尾追加showFirstUnique()$O(N^2)$对每个元素做一次全队列计数空间复杂度$O(N)$其中 $K$ 是构造时传入初始数组的长度$N$ 是截至目前含构造函数已加入队列的元素总数。三、方法二队列 唯一性状态哈希表惰性删除思路Intuition暴力法的瓶颈在于showFirstUnique()每次都要重新统计每个元素出现的次数。但我们可以换个角度——在add()时就同步维护好每个元素的唯一性状态让showFirstUnique()不必再统计。具体做法是用一个哈希表isUnique记录每个值当前是否唯一用队列保持插入顺序。当需要展示首个唯一元素时从队首开始清理只要队首元素被标记为不唯一就把它弹出直到找到唯一的元素或队列为空。这里的删除是**惰性lazy**的元素在变为不唯一时并不立即出队而是等它堵到队首、阻碍查询时才被清除。由于每个元素最多出队一次均摊下来仍然是 O(1)。算法步骤构造函数对初始数组中的每个数字调用一次add()。注意这里调用的是FirstUnique自己的add方法会同时维护队列与哈希表而不是直接操作队列——文档源码注释特别提醒Notice that were calling the add method of FirstUnique; not of the queue。add(value)若该值第一次出现在哈希表中标记为true唯一并加入队列若该值已出现过第二次及以后在哈希表中标记为false不唯一不重复入队。showFirstUnique()循环只要队首元素在哈希表中被标记为不唯一就popleft/pop弹出它若队列非空返回队首元素注意只读不删否则返回-1。一个关键不变量是只要某个值在队列中它就一定在isUnique中——add()的实现保证了这一点所以showFirstUnique()里可以直接用is_unique[queue[0]]查询而不必担心键缺失。多语言实现class FirstUnique: def __init__(self, nums: List[int]): self._queue deque(nums) self._is_unique {} for num in nums: # Notice that were calling the add method of FirstUnique; not of the queue. self.add(num) def showFirstUnique(self) - int: # We need to start by cleaning the queue of any non-uniques at the start. # Note that we know that if a value is in the queue, then it is also in # is_unique, as the implementation of add() guarantees this. while self._queue and not self._is_unique[self._queue[0]]: self._queue.popleft() # Check if there is still a value left in the queue. There might be no uniques. if self._queue: return self._queue[0] # We dont want to actually *remove* the value. return -1 def add(self, value: int) - None: # Case 1: We need to add the number to the queue and mark it as unique. if value not in self._is_unique: self._is_unique[value] True self._queue.append(value) # Case 2 and 3: We need to mark the number as no longer unique. else: self._is_unique[value] Falseclass FirstUnique { private QueueInteger queue new ArrayDeque(); private MapInteger, Boolean isUnique new HashMap(); public FirstUnique(int[] nums) { for (int num : nums) { // Notice that were calling the add method of FirstUnique; not of the queue. this.add(num); } } public int showFirstUnique() { // We need to start by cleaning the queue of any non-uniques at the start. // Note that we know that if a value is in the queue, then it is also in // isUnique, as the implementation of add() guarantees this. while (!queue.isEmpty() !isUnique.get(queue.peek())) { queue.remove(); } // Check if there is still a value left in the queue. There might be no uniques. if (!queue.isEmpty()) { return queue.peek(); // We dont want to actually *remove* the value. } return -1; } public void add(int value) { // Case 1: We need to add the number to the queue and mark it as unique. if (!isUnique.containsKey(value)) { isUnique.put(value, true); queue.add(value); // Case 2 and 3: We need to mark the number as no longer unique. } else { isUnique.put(value, false); } } }class FirstUnique { private: queueint q; unordered_mapint, bool isUnique; public: FirstUnique(vectorint nums) { for (int num : nums) { this-add(num); } } int showFirstUnique() { while (!q.empty() !isUnique[q.front()]) { q.pop(); } if (!q.empty()) { return q.front(); } return -1; } void add(int value) { if (isUnique.find(value) isUnique.end()) { isUnique[value] true; q.push(value); } else { isUnique[value] false; } } };class FirstUnique { /** * param {number[]} nums */ constructor(nums) { this._queue nums.slice(); this._is_unique {}; for (let num of nums) { this.add(num); } } /** * return {number} */ showFirstUnique() { while (this._queue.length 0 !this._is_unique[this._queue[0]]) { this._queue.shift(); } if (this._queue.length 0) { return this._queue[0]; } return -1; } /** * param {number} value * return {void} */ add(value) { if (!(value in this._is_unique)) { this._is_unique[value] true; this._queue.push(value); } else { this._is_unique[value] false; } } }public class FirstUnique { private Queueint queue new Queueint(); private Dictionaryint, bool isUnique new Dictionaryint, bool(); public FirstUnique(int[] nums) { foreach (int num in nums) { Add(num); } } public int ShowFirstUnique() { while (queue.Count 0 !isUnique[queue.Peek()]) { queue.Dequeue(); } if (queue.Count 0) { return queue.Peek(); } return -1; } public void Add(int value) { if (!isUnique.ContainsKey(value)) { isUnique[value] true; queue.Enqueue(value); } else { isUnique[value] false; } } }type FirstUnique struct { queue []int isUnique map[int]bool } func Constructor(nums []int) FirstUnique { fu : FirstUnique{ queue: []int{}, isUnique: make(map[int]bool), } for _, num : range nums { fu.Add(num) } return fu } func (this *FirstUnique) ShowFirstUnique() int { for len(this.queue) 0 !this.isUnique[this.queue[0]] { this.queue this.queue[1:] } if len(this.queue) 0 { return this.queue[0] } return -1 } func (this *FirstUnique) Add(value int) { if _, exists : this.isUnique[value]; !exists { this.isUnique[value] true this.queue append(this.queue, value) } else { this.isUnique[value] false } }class FirstUnique(nums: IntArray) { private val queue ArrayDequeInt() private val isUnique HashMapInt, Boolean() init { for (num in nums) { add(num) } } fun showFirstUnique(): Int { while (queue.isNotEmpty() isUnique[queue.first()] false) { queue.removeFirst() } if (queue.isNotEmpty()) { return queue.first() } return -1 } fun add(value: Int) { if (value !in isUnique) { isUnique[value] true queue.addLast(value) } else { isUnique[value] false } } }class FirstUnique { private var queue: [Int] private var isUnique: [Int: Bool] init(_ nums: [Int]) { queue [] isUnique [:] for num in nums { add(num) } } func showFirstUnique() - Int { while !queue.isEmpty isUnique[queue[0]] false { queue.removeFirst() } if !queue.isEmpty { return queue[0] } return -1 } func add(_ value: Int) { if isUnique[value] nil { isUnique[value] true queue.append(value) } else { isUnique[value] false } } }struct FirstUnique { queue: VecDequei32, is_unique: HashMapi32, bool, } impl FirstUnique { fn new(nums: Veci32) - Self { let mut fu FirstUnique { queue: VecDeque::new(), is_unique: HashMap::new(), }; for num in nums { fu.add(num); } fu } fn show_first_unique(mut self) - i32 { while let Some(front) self.queue.front() { if !self.is_unique[front] { self.queue.pop_front(); } else { return front; } } -1 } fn add(mut self, value: i32) { if !self.is_unique.contains_key(value) { self.is_unique.insert(value, true); self.queue.push_back(value); } else { self.is_unique.insert(value, false); } } }复杂度分析时间复杂度构造函数$O(K)$add()$O(1)$showFirstUnique()$O(1)$均摊 amortized空间复杂度$O(N)$其中 $K$ 是构造时传入初始数组的长度$N$ 是截至目前含构造函数已加入队列的元素总数。为什么是均摊 O(1)因为队列里的每个元素至多只会被弹出一次showFirstUnique()的清理总工作量被限制在 $O(N)$ 以内分摊到多次调用后每次就是常数级。这与单调栈、滑动窗口等每个元素至多进出一次的均摊分析思路完全一致。四、方法三LinkedHashSet 作队列 唯一性状态哈希表主动删除思路Intuition方法二的惰性删除已经足够好但showFirstUnique()偶尔会触发一次较长的清理循环。如果希望它成为真正严格意义的 O(1)可以把清理工作从查询阶段提前到add()阶段一旦某个元素第二次出现、变得不唯一就立刻把它从保序集合中删除。这需要一个既能按值 O(1) 删除、又能保持插入顺序、还能 O(1) 拿到首元素的数据结构——正是LinkedHashSetJava 的LinkedHashSet、Kotlin 的LinkedHashSet、JavaScript 的Set、Python 的OrderedDict等以及 C/C#/Go/Swift 中双向链表 位置索引的手工等价物。算法步骤构造函数对初始数组中的每个数字调用一次add()。add(value)Case 1第一次出现在哈希表中标记为唯一并加入保序集合Case 2第二次出现当前仍唯一在哈希表中标记为不唯一并从保序集合中删除该值Case 3第三次及以上什么也不做——元素早已在第二次出现时被移出集合。showFirstUnique()若集合非空返回其第一个元素否则返回-1。整个过程没有任何清理循环。可以看到保序集合中永远只存放当前仍唯一的元素所以取第一个就是答案showFirstUnique()变成了名副其实的 O(1)。多语言实现# In Python, we have to make do with the OrderedDict class. We can use it as a Set by setting # the values to None. class FirstUnique: def __init__(self, nums: List[int]): self._queue OrderedDict() self._is_unique {} for num in nums: # Notice that were calling the add method of FirstUnique; not of the queue. self.add(num) def showFirstUnique(self) - int: # Check if there is still a value left in the queue. There might be no uniques. if self._queue: # We dont want to actually *remove* the value. # Seeing as OrderedDict has no get first method, the way that we can get # the first value is to create an iterator, and then get the next value # from that. Note that this is O(1). return next(iter(self._queue)) return -1 def add(self, value: int) - None: # Case 1: We need to add the number to the queue and mark it as unique. if value not in self._is_unique: self._is_unique[value] True self._queue[value] None # Case 2: We need to mark the value as no longer unique and then # remove it from the queue. elif self._is_unique[value]: self._is_unique[value] False self._queue.pop(value) # Case 3: We dont need to do anything; the number was removed from the queue # the second time it occurred.class FirstUnique { private SetInteger setQueue new LinkedHashSet(); private MapInteger, Boolean isUnique new HashMap(); public FirstUnique(int[] nums) { for (int num : nums) { this.add(num); } } public int showFirstUnique() { // If the queue contains values, we need to get the first one from it. // We can do this by making an iterator, and getting its first item. if (!setQueue.isEmpty()) { return setQueue.iterator().next(); } return -1; } public void add(int value) { // Case 1: This value is not yet in the data structure. // It should be ADDED. if (!isUnique.containsKey(value)) { isUnique.put(value, true); setQueue.add(value); // Case 2: This value has been seen once, so is now becoming // non-unique. It should be REMOVED. } else if (isUnique.get(value)) { isUnique.put(value, false); setQueue.remove(value); } } }class FirstUnique { private: std::listint setQueue; std::unordered_mapint, std::listint::iterator queuePosition; std::unordered_mapint, bool isUnique; public: FirstUnique(vectorint nums) { for (int num : nums) { this-add(num); } } int showFirstUnique() { // If the queue contains values, we need to get the first one from it. // We can do this by making an iterator, and getting its first item. if (!setQueue.empty()) { return setQueue.front(); } return -1; } void add(int value) { // Case 1: This value is not yet in the data structure. // It should be ADDED. if (isUnique.find(value) isUnique.end()) { isUnique[value] true; setQueue.push_back(value); queuePosition[value] std::prev(setQueue.end()); // Case 2: This value has been seen once, so is now becoming // non-unique. It should be REMOVED. } else if (isUnique[value]) { isUnique[value] false; setQueue.erase(queuePosition[value]); queuePosition.erase(value); } } };class FirstUnique { /** * param {number[]} nums */ constructor(nums) { this.setQueue new Set(); this.isUnique new Map(); for (const num of nums) { this.add(num); } } /** * return {number} */ showFirstUnique() { // If the queue contains values, we need to get the first one from it. // We can do this by making an iterator, and getting its first item. if (this.setQueue.size 0) { return this.setQueue.values().next().value; } return -1; } /** * param {number} value * return {void} */ add(value) { // Case 1: This value is not yet in the data structure. // It should be ADDED. if (!this.isUnique.has(value)) { this.isUnique.set(value, true); this.setQueue.add(value); // Case 2: This value has been seen once, so is now becoming // non-unique. It should be REMOVED. } else if (this.isUnique.get(value)) { this.isUnique.set(value, false); this.setQueue.delete(value); } } }public class FirstUnique { private LinkedListint setQueue new LinkedListint(); private Dictionaryint, LinkedListNodeint queuePosition new Dictionaryint, LinkedListNodeint(); private Dictionaryint, bool isUnique new Dictionaryint, bool(); public FirstUnique(int[] nums) { foreach (int num in nums) { Add(num); } } public int ShowFirstUnique() { if (setQueue.Count 0) { return setQueue.First.Value; } return -1; } public void Add(int value) { if (!isUnique.ContainsKey(value)) { isUnique[value] true; setQueue.AddLast(value); queuePosition[value] setQueue.Last; } else if (isUnique[value]) { isUnique[value] false; setQueue.Remove(queuePosition[value]); queuePosition.Remove(value); } } }type FirstUnique struct { setQueue *list.List queuePosition map[int]*list.Element isUnique map[int]bool } func Constructor(nums []int) FirstUnique { fu : FirstUnique{ setQueue: list.New(), queuePosition: make(map[int]*list.Element), isUnique: make(map[int]bool), } for _, num : range nums { fu.Add(num) } return fu } func (this *FirstUnique) ShowFirstUnique() int { if this.setQueue.Len() 0 { return this.setQueue.Front().Value.(int) } return -1 } func (this *FirstUnique) Add(value int) { if _, exists : this.isUnique[value]; !exists { this.isUnique[value] true elem : this.setQueue.PushBack(value) this.queuePosition[value] elem } else if this.isUnique[value] { this.isUnique[value] false this.setQueue.Remove(this.queuePosition[value]) delete(this.queuePosition, value) } }class FirstUnique(nums: IntArray) { private val setQueue LinkedHashSetInt() private val isUnique HashMapInt, Boolean() init { for (num in nums) { add(num) } } fun showFirstUnique(): Int { if (setQueue.isNotEmpty()) { return setQueue.iterator().next() } return -1 } fun add(value: Int) { if (value !in isUnique) { isUnique[value] true setQueue.add(value) } else if (isUnique[value] true) { isUnique[value] false setQueue.remove(value) } } }class FirstUnique { private var setQueue: [Int] [] private var queuePosition: [Int: Int] [:] private var isUnique: [Int: Bool] [:] init(_ nums: [Int]) { for num in nums { add(num) } } func showFirstUnique() - Int { if !setQueue.isEmpty { return setQueue[0] } return -1 } func add(_ value: Int) { if isUnique[value] nil { isUnique[value] true queuePosition[value] setQueue.count setQueue.append(value) } else if isUnique[value] true { isUnique[value] false if let pos queuePosition[value] { setQueue.remove(at: pos) queuePosition.removeValue(forKey: value) for (key, idx) in queuePosition { if idx pos { queuePosition[key] idx - 1 } } } } } }struct FirstUnique { set_queue: BTreeSet(usize, i32), // (insertion order, value) is_unique: HashMapi32, bool, order: HashMapi32, usize, counter: usize, } impl FirstUnique { fn new(nums: Veci32) - Self { let mut fu FirstUnique { set_queue: BTreeSet::new(), is_unique: HashMap::new(), order: HashMap::new(), counter: 0, }; for num in nums { fu.add(num); } fu } fn show_first_unique(self) - i32 { if let Some((_, val)) self.set_queue.iter().next() { val } else { -1 } } fn add(mut self, value: i32) { if !self.is_unique.contains_key(value) { self.is_unique.insert(value, true); self.order.insert(value, self.counter); self.set_queue.insert((self.counter, value)); self.counter 1; } else if *self.is_unique.get(value).unwrap() { self.is_unique.insert(value, false); if let Some(ord) self.order.get(value) { self.set_queue.remove((ord, value)); } } } }各语言中保序可删集合的等价实现方法三在不同语言里依赖的底层结构各不相同文档源码给出了每种语言的具体选型articles/first-unique-number.md语言保序结构关键点PythonOrderedDict以值作键、None作值充当 SetOrderedDict没有取第一个方法用next(iter(dict))以 O(1) 拿到首键JavaLinkedHashSetiterator().next()取首元素remove(value)按值删除KotlinLinkedHashSet与 Java 完全同构JavaScript原生Set按插入顺序迭代values().next().value取首元素Cstd::list 迭代器索引哈希表queuePosition存list::iterator实现 O(1) 定点删除C#LinkedList 节点索引Dictionaryint, LinkedListNodeint存节点引用Remove(node)为 O(1)Gocontainer/list*list.Element索引PushBack返回元素指针Remove(elem)按引用删除Swift数组 下标索引无内建保序删除集合删除后需把后续下标整体左移O(N) 补偿RustBTreeSet(usize, i32) 单调计数器用插入序号 值二元组排序等价模拟有序集合BTreeSet删除/取最小均为 O(log N)从源码结构看Swift 与 Rust 的版本由于语言标准库缺少插入序 O(1) 按值删除的容器分别退化为数组 下标维护与BTreeSet 计数器的近似方案前者删除后需重建索引后者单次操作为 O(log N)——它们属于空间换正确性的语言适配并不改变算法整体设计思想。复杂度分析时间复杂度构造函数$O(K)$add()$O(1)$Python / Java / C / C# / Go / Kotlin / JavaScript 版本showFirstUnique()$O(1)$空间复杂度$O(N)$其中 $K$ 是构造时传入初始数组的长度$N$ 是截至目前含构造函数已加入队列的元素总数。与方法二相比区别在于方法二的 $O(1)$ 是均摊的清理工作平摊到多次查询方法三则是每次调用都严格 O(1)清理工作在add()时即时完成查询阶段零循环。二者总工作量相同方法三的常数更稳定代价是add()内部多了一次从集合中按值删除的操作。五、三种方案复杂度与适用场景对比方案构造函数add()showFirstUnique()空间删除策略适用场景暴力解法$O(K)$$O(1)$$O(N^2)$$O(N)$无每次全量统计数据量小、查询频率极低队列 状态哈希表$O(K)$$O(1)$$O(1)$ 均摊$O(N)$惰性删除查询时清理队首通用首选实现最简洁LinkedHashSet 状态哈希表$O(K)$$O(1)$$O(1)$ 严格$O(N)$主动删除add()时即时移除查询最频繁、追求稳定延迟三条路线的演进本质是把判重从查询时计算前置到写入时维护暴力法在查询时全量数数 → 每次 $O(N^2)$引入哈希表状态后判重变成 $O(1)$查询只剩队首清理 → 均摊 $O(1)$再用保序可删集合把清理也前置 → 严格 $O(1)$。从仓库的文档组织看这道题与 articles/lru-cache.md同样需要按访问序 O(1) 查改、articles/implement-queue-using-stacks.md队列语义的模拟实现同属设计数据结构家族解法一脉相承。六、常见陷阱Common Pitfalls文档在最后专门总结了三个最容易写错的点articles/first-unique-number.md这里逐条展开陷阱一初始数组被重复加入队列在队列 哈希表类方案中如果构造时既直接向队列 push 初始元素、又对每个元素调用一次add()就会把元素重复入队破坏唯一性判定。正确做法只有两种二选一不能混用只遍历初始数组并对每个元素调用add()由add()统一维护队列与哈希表或者完全不调用add()手动同时维护两个结构。混用两种做法会让队列中出现重复元素进而导致showFirstUnique()返回错误结果。陷阱二查询前没有清理队首的过期非唯一元素惰性删除方案里队列中可能残留着已经变为不唯一、但还堵在队首的过期元素。如果showFirstUnique()不先弹出它们就直接返回队首就会返回一个非唯一的数字。每次返回前都必须依据哈希表状态从队首开始弹出所有已失效的条目再取新的队首。陷阱三重复添加时错误地恢复唯一性状态当一个元素第三次、第四次被添加时它的唯一性状态必须保持false。一个常见 bug 是在add()的 else 分支里无脑把状态设回true或把元素重新加回集合——这会让已经出现的元素复活成唯一彻底打乱结果。正确的状态转移是单向的、不可逆的从未出现 (not seen) → 唯一 (unique) → 不唯一 (non-unique)一旦进入non-unique就永远不能回头。用方法三的 Case 结构表述即if 未出现过: 标记 unique加入集合 else if 当前 unique: 标记 non-unique移出集合 else: 什么都不做七、总结与同类问题延伸「First Unique Number」的完整解题路径可以概括为一条主线保序容器队列 / 保序集合负责第一个哈希表负责唯一二者通过add()时的状态维护协同工作三种方法只是在何时清理不唯一元素上做了不同取舍。掌握这道题后可以继续挑战仓库中这些结构相近的设计题进一步巩固保序 判重的心智模型articles/first-unique-character-in-a-string.md字符串场景下求第一个唯一字符是本题的静态版本articles/largest-unique-number.md从数组中找最大的唯一数同一判重思想的不同出口articles/lru-cache.md把唯一性状态换成最近使用序同样依赖哈希表 保序结构的组合articles/kth-largest-integer-in-a-stream.md同为流式数据 持续查询的设计题可对比其使用堆而非队列的原因。本文全部解法与多语言源码均出自仓库文档 articles/first-unique-number.md仓库整体为 NeetCode.io 的多语言题解集合见 README.md你可以在对应语言目录python/、java/、cpp/等中查阅同题的其他工程化实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考