企业官网建设流程全解析

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的类，其核心是在不断有数据流入的前提下，随时回答"当前所有已见元素中，第一个只出现过一次的元素是谁"。

标准接口包含三个方法：

举例来说，若初始数组为[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 don't want to actuallyremovethe value"（articles/first-unique-number.md）。这与队列的经典peek语义一致。

它的难点在于：唯一性状态是动态变化的——一个元素在第二次出现时就从"唯一"降级为"不唯一"，且这种降级会发生在任意位置，不一定在队首。因此"保序"与"快速判重"必须同时满足，这正是本仓库 README.md 中归类为队列（Queue）与哈希表（Hash Map）综合题的原因。

前置知识：三个基础数据结构

动手前需要熟悉：

• 队列（Queue）：FIFO（先进先出）结构，用于维护元素的插入顺序，保证能取到"第一个"。
• 哈希表（Hash Map）：以 O(1) 时间跟踪每个元素的计数或唯一性状态，这是把showFirstUnique()从 O(N) 降到 O(1) 的关键。
• LinkedHashSet / OrderedDict：把哈希表 O(1) 查找与"插入顺序保持"两者合一，让"按值删除 + 取第一个"都能高效完成。

二、方法一：暴力解法（Brute Force）

思路（Intuition）

最直接的想法：把所有数字放进一个队列。调用showFirstUnique()时，从头到尾扫描队列，对每个元素统计它在整个队列中出现的次数，返回第一个计数恰好为 1的元素。

这个方法正确性毋庸置疑，但代价是每次查询都要做一轮完整的扫描与计数，复杂度随数据规模急剧增长。

算法步骤

1. 构造函数：将初始数组的所有数字放入队列。
2. add(value)：直接把值追加到队列末尾（O(1)）。
3. 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 Queue<Integer> 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: queue<int> q; public: FirstUnique(vector<int>& nums) { for (int num : nums) { q.push(num); } } int showFirstUnique() { queue<int> temp = q; while (!temp.empty()) { int num = temp.front(); temp.pop(); int count = 0; queue<int> 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 Queue<int> queue = new Queue<int>(); 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 = ArrayDeque<Int>() 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: VecDeque<i32>, } impl FirstUnique { fn new(nums: Vec<i32>) -> Self { let queue: VecDeque<i32> = 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)。

算法步骤

1. 构造函数：对初始数组中的每个数字调用一次add()。注意这里调用的是FirstUnique自己的add方法（会同时维护队列与哈希表），而不是直接操作队列——文档源码注释特别提醒："Notice that we're calling the 'add' method of FirstUnique; not of the queue"。
2. add(value)：
   • 若该值第一次出现：在哈希表中标记为true（唯一），并加入队列；
   • 若该值已出现过（第二次及以后）：在哈希表中标记为false（不唯一），不重复入队。
3. 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 we're 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 don't 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] = False

class FirstUnique { private Queue<Integer> queue = new ArrayDeque<>(); private Map<Integer, Boolean> isUnique = new HashMap<>(); public FirstUnique(int[] nums) { for (int num : nums) { // Notice that we're 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 don't 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: queue<int> q; unordered_map<int, bool> isUnique; public: FirstUnique(vector<int>& 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 Queue<int> queue = new Queue<int>(); private Dictionary<int, bool> isUnique = new Dictionary<int, 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 = ArrayDeque<Int>() private val isUnique = HashMap<Int, 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: VecDeque<i32>, is_unique: HashMap<i32, bool>, } impl FirstUnique { fn new(nums: Vec<i32>) -> 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) 拿到首元素的数据结构——正是LinkedHashSet（Java 的LinkedHashSet、Kotlin 的LinkedHashSet、JavaScript 的Set、Python 的OrderedDict等），以及 C++/C#/Go/Swift 中"双向链表 + 位置索引"的手工等价物。

算法步骤

1. 构造函数：对初始数组中的每个数字调用一次add()。
2. add(value)：
   • Case 1（第一次出现）：在哈希表中标记为唯一，并加入保序集合；
   • Case 2（第二次出现，当前仍唯一）：在哈希表中标记为不唯一，并从保序集合中删除该值；
   • Case 3（第三次及以上）：什么也不做——元素早已在第二次出现时被移出集合。
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 we're 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 don't 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 don't need to do anything; the number was removed from the queue # the second time it occurred.

class FirstUnique { private Set<Integer> setQueue = new LinkedHashSet<>(); private Map<Integer, 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::list<int> setQueue; std::unordered_map<int, std::list<int>::iterator> queuePosition; std::unordered_map<int, bool> isUnique; public: FirstUnique(vector<int>& 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 LinkedList<int> setQueue = new LinkedList<int>(); private Dictionary<int, LinkedListNode<int>> queuePosition = new Dictionary<int, LinkedListNode<int>>(); private Dictionary<int, bool> isUnique = new Dictionary<int, 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 = LinkedHashSet<Int>() private val isUnique = HashMap<Int, 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: HashMap<i32, bool>, order: HashMap<i32, usize>, counter: usize, } impl FirstUnique { fn new(nums: Vec<i32>) -> 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）：

从源码结构看，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()内部多了一次"从集合中按值删除"的操作。

五、三种方案复杂度与适用场景对比

三条路线的演进本质是把"判重"从查询时计算前置到写入时维护：

1. 暴力法在查询时全量数数 → 每次 $O(N^2)$；
2. 引入哈希表状态后，判重变成 $O(1)$，查询只剩队首清理 → 均摊 $O(1)$；
3. 再用保序可删集合把清理也前置 → 严格 $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