教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南基于「宫水三叶的刷题日记」仓库中的 LeetCode 2336. 无限集中的最小数字题解深入剖析一道中等难度的数据结构设计题。本题是「优先队列堆 哈希表」两大基础数据结构的经典组合应用面对一个包含全部正整数的无限集合需要支持取出最小元素与回填元素两种操作。读完本文你将掌握用idx指针表示连续区间、用小根堆承载离散回填元素、用哈希表或布尔数组做去重的完整建模思路并能在 Java、C、Python、TypeScript 四种语言下写出可提交的高效实现。题目描述与核心难点现有一个包含所有正整数的集合 $[1, 2, 3, 4, 5, ...]$需要实现SmallestInfiniteSet类SmallestInfiniteSet()初始化对象以包含所有正整数int popSmallest()移除并返回该无限集中的最小整数void addBack(int num)如果正整数num不存在于无限集中则将其添加到集合中。示例调用序列输入 [SmallestInfiniteSet, addBack, popSmallest, popSmallest, popSmallest, addBack, popSmallest, popSmallest, popSmallest] [[], [2], [], [], [], [1], [], [], []] 输出 [null, null, 1, 2, 3, null, 1, 4, 5] 解释 SmallestInfiniteSet smallestInfiniteSet new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 已经在集合中所以不做任何变更。 smallestInfiniteSet.popSmallest(); // 返回 1 因为 1 是最小的整数并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 2 并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 3 并将其从集合中移除。 smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。 smallestInfiniteSet.popSmallest(); // 返回 1 因为 1 在上一步中被添加到集合中 // 且 1 是最小的整数并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 4 并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 5 并将其从集合中移除。题目提示$1 num 1000$最多调用popSmallest和addBack方法共计 $1000$ 次。核心难点在于集合是无限的不可能显式地把所有正整数存进容器同时又要求popSmallest永远返回当前集合中的最小整数且addBack可以回填任意被弹出的数。这要求我们抽象出集合的结构而不是穷举存储。解题思路将无限集拆成连续段 离散段原题解给出了一种非常简洁的建模使用idx代表顺序弹出的集合左边界$[idx, \infty]$ 范围内的数均为待弹出起始时有 $idx 1$。也就是说把无限集合在逻辑上一分为二连续段[idx, ∞)所有大于等于idx的正整数天然都在集合中尚未被弹出。对这一段的操作复杂度是 $O(1)$因为只需取出idx并自增即可离散段所有小于idx但被addBack回填过的数。它们以离散状态存在需要容器保存并支持取出最小值——自然联想到小根堆优先队列。当调用addBack往集合添加数值x时分三种情况处理情况条件处理方式已在集合中$x \geq idx$数值本身就存在于连续段中忽略该添加操作恰好补齐边界$x idx - 1$数值刚好位于边界左侧更新 $idx idx - 1$需要入堆$x idx - 1$将数值加入小根堆并用哈希表标记防止重复弹出这里需要特别强调为什么小根堆必须配合哈希表小根堆只有返回最小值的能力并没有去重能力。如果不加标记同一个被回填的数可能被addBack多次写入堆中导致popSmallest重复弹出同一个值破坏集合的语义。因此在addBack入堆时同步置vis[x] true在popSmallest出堆时同步置vis[ans] false。该做法的时间复杂度为连续段操作 $O(1)$离散段堆操作 $O(\log{n})$其中 $n$ 为调用addBack的最大次数总空间复杂度 $O(n)$。四种语言的完整实现原题解给出了 Java、C、Python、TypeScript 四种实现细节略有差异但核心逻辑完全一致均可直接提交Javaclass SmallestInfiniteSet { boolean[] vis new boolean[1010]; PriorityQueueInteger q new PriorityQueue((a,b)-a-b); int idx 1; public int popSmallest() { int ans -1; if (!q.isEmpty()) { ans q.poll(); vis[ans] false; } else { ans idx; } return ans; } public void addBack(int x) { if (x idx || vis[x]) return ; if (x idx - 1) { idx--; } else { q.add(x); vis[x] true; } } }注意 Java 中PriorityQueue默认即为小根堆升序(a,b)-a-b是显式声明比较器可读性更好。Cclass SmallestInfiniteSet { public: vectorbool vis; priority_queueint, vectorint, greaterint q; int idx; SmallestInfiniteSet() : idx(1) { vis.resize(1010, false); } int popSmallest() { int ans -1; if (!q.empty()) { ans q.top(); q.pop(); vis[ans] false; } else { ans idx; } return ans; } void addBack(int x) { if (x idx || vis[x]) return; if (x idx - 1) { idx--; } else { q.push(x); vis[x] true; } } };C 的priority_queue默认是大根堆必须用greaterint作为比较器显式构造小根堆同时popSmallest中要先取top()再pop()。Pythonclass SmallestInfiniteSet: def __init__(self): self.vis [False] * 1010 self.q [] self.idx 1 def popSmallest(self): ans -1 if self.q: ans heapq.heappop(self.q) self.vis[ans] False else: ans self.idx self.idx 1 return ans def addBack(self, x): if x self.idx or self.vis[x]: return if x self.idx - 1: self.idx - 1 else: heapq.heappush(self.q, x) self.vis[x] TruePython 需在文件头部引入import heapq。heapq模块对列表原地建堆heappush/heappop均为 $O(\log{n})$。TypeScriptclass SmallestInfiniteSet { vis: boolean[] Array(1010).fill(false); q: number[] []; idx: number 1; popSmallest(): number { let ans: number -1; if (this.q.length ! 0) { ans this.q.sort((a, b) a - b).shift() as number; this.vis[ans] false; } else { ans this.idx; } return ans; } addBack(x: number): void { if (x this.idx || this.vis[x]) return; if (x this.idx - 1) { this.idx--; } else { this.q.push(x); this.vis[x] true; } } }TypeScript 没有内置堆这里用数组排序后取头部模拟小根堆的语义适用于本题 $1000$ 次调用的小数据规模追求更严格的 $O(\log{n})$ 时可用手写堆替代。时间复杂度插入和取出的最坏复杂度为 $O(\log{n})$空间复杂度$O(n)$。从源码结构看边界处理与数组容量设计结合本题实现可以注意到两个容易被忽视的细节它们直接来源于原题解的代码结构1. 为什么vis数组长度为 1010题目提示 $1 num 1000$即addBack传入的值最大为 1000。由于数组下标从 0 开始长度为 1010 的布尔数组足以覆盖全部合法取值同时留出少量余量。在 Java 中boolean[]默认初始化为falsePython 中显式[False] * 1010C 中通过构造函数vis.resize(1010, false)完成初始化。2.x idx - 1分支的本质是什么当回填的数恰好是当前边界的前一个数时说明离散段与连续段衔接上了此时不需要入堆直接把idx左移一位即可将x并回连续段。这也是整个解法中最精妙的一步——它避免了把大量连续回填的数逐个塞进堆里使连续段操作始终保持 $O(1)$。从仓库索引看本题的算法定位本题在原仓库中被归类为「优先队列堆」与「哈希表」双标签分别对应仓库中的 堆.md 与 哈希表.md 两个索引页。在堆索引页中本题与 23. 合并K个升序链表、215. 数组中的第K个最大元素、295. 数据流的中位数、703. 数据流中的第 K 大元素 等同列于堆主题之下共同构成了小根堆维护动态最值的完整题型谱系。其中 703. 数据流中的第 K 大元素 与本体的对比尤为直观703 用容量为 k 的小根堆在流式数据中维护第 k 大核心是堆容量的上下界管理而 2336 用小根堆 去重标记维护动态集合的最小值核心是连续段与离散段的划分。两者都体现了堆擅长回答最值查询、但对元素去重无能为力这一共同特点需要搭配哈希表或数组标记补齐语义。复杂度分析小结维度连续段$x \geq idx$ 相关操作离散段堆操作popSmallest$O(1)$直接取idx$O(\log{n})$堆顶出堆addBack$O(1)$比较x与idx关系$O(\log{n})$入堆调整空间$O(1)$$O(n)$堆内元素 vis标记其中 $n$ 为调用addBack的最大次数。在题目给定的数据范围调用次数 $\leq 1000$下该解法无论时间还是空间都远优于暴力维护完整集合的方案是本题的标准最优解之一。总结「无限集中的最小数字」是一道典型的数据结构组合设计题单看小根堆与哈希表都不难难点在于将无限抽象为连续段 离散段的建模思路以及用idx指针让连续段操作降到 $O(1)$。该思路与仓库中其他堆类题目如 703、295一脉相承掌握后可以迁移到动态集合最值维护一类问题的通解中。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐AlgoNote 题解LeetCode 373「查找和最小的 K 对数字」——最小堆优先队列求 Top-K 最小和数对AlgoNote 题解LeetCode 373「查找和最小的 K 对数字」——最小堆优先队列求 Top K 最小和数对 本文是《AlgoNote 算法通关教程文档知识库LeetCode 599「两个列表的最小索引总和」题解AlgoNote 哈希表查索引的最小和求法LeetCode 599「两个列表的最小索引总和」题解AlgoNote 哈希表查索引的最小和求法 本篇题解对应 AlgoNote https://link.g教程文档知识库LogicStack-LeetCode减小和重新排列数组后的最大元素LogicStack LeetCode减小和重新排列数组后的最大元素 在算法问题中数组的重新排列和调整是常见题型。本文将详细解析LeetCode中等难度题目教程文档上一篇LanzouAPI 蓝奏云直链解析完整指南5 分钟从分享链接拿到可下载直链下一篇LanzouAPI 蓝奏云直链解析使用指南如何把分享链接变成真实下载地址创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考