我们正在处理正整数流。在任何时间点，都可以向我们询问一个答案，答案是我们尚未看到的最小正数。
一个可以假设两个API。
void processnext(int val)
int getSmallestNotSeen()
我们可以假设数字以[1,10 ^ 6]范围为界。将此范围设为N。
这是我的解决方案。
让我们采用大小为10 ^ 6的数组。
每当调用processnext（val）时，我们都会将array [val]标记为1。我们在此数组上创建一个求和段树。这将是段树中的点更新。
每当调用getSmallestNotSeen（）时，我都会找到最小索引j，使得总和[1..j]小于j。我使用二进制搜索找到j。
processnext（val）-> O（1）
getSmallestNotSeen（）-> O（（logN）^ 2）
我在想，也许还有更好的东西。或可以改善上述解决方案。
制作一个id->节点（双向链接列表的节点）的映射，并初始化10 ^ 6个节点，每个节点都指向其邻居。将最小值初始化为一。
processNext（val）：检查节点是否存在。如果是这样，请将其删除，并将其邻居指向彼此。如果您删除的节点没有左邻居（即最小），则将最小值更新为右邻居。
getSmallestNotSeen（）：返回最小值
预处理是线性时间和线性内存。之后的一切都是固定的时间。
,bool array[10^6] = {false,false,... }
int min = 1
void processNext(int val) {
array[val] = true // A
while (array[min]) // B
min++ // C
}
int getSmallestNotSeen() {
return min
}
时间复杂度：
O(1) O(1) 分析：
如果processNext被调用k次，并且n是存储在min中的最大值（可以在getSmallestNotSeen中返回），则：
A行将准确执行k次，B行将准确执行k + n次，并且C行将准确执行n次。此外，n永远不会大于k，因为要使min达到n，就需要连续不断的n {{ 1}}在数组中，总共只能有true k在数组中。因此，行true最多可以执行B次，行2 * k最多可以执行C次。
空间复杂度：
可以使用HashMap而不使用数组，而无需对伪代码进行任何其他更改（HashMap中不存在的键应评估为k）。那么，空间复杂度为false。此外，您可以修剪小于O(k)的键，从而在某些情况下节省空间：
min如果流值稳定增加，则这种修剪技术可能最有效。
,如果processNext调用的数量（即流的长度）与 N 的范围相比非常小，则可以通过存储连续的范围，而不是所有可能的单个数字。当 N 的范围可能更大时，例如[1，2 64 -1]
我建议使用以[开始，结束]范围为元素并且具有自平衡功能（例如AVL，红黑...）的二进制搜索树。
使用一个（根）节点初始化树：[1，Infinity]
每当用val提取新值processNext时，就使用二进制搜索找到包含val的范围[start，end]。
如果范围的大小为1（因此仅包含val），请执行删除该节点的操作（根据树规则）
否则，如果val是范围的边界值，则只需更新该节点中的范围，不包括val。
否则，将范围分为两部分。使用两个范围之一（由余额信息决定）更新节点，然后让另一个范围向下筛选到新的叶子（并在需要时重新平衡）。
在树中维护对具有最小起始值的节点的引用。仅当此节点在processNext期间被删除时，才需要在树中向上或向下遍历以找到下一个（按顺序）节点。当节点分裂时（请参见上文），并确定将下部放入新的叶子中，则需要将引用更新为该叶子。
getSmallestNotSeen函数将从该最小范围节点返回起始值。
空间复杂度为 O（S），其中 S 是流的长度
processNext的时间复杂度为 O（log（S））
getSmallestNotSeen的时间复杂度为 O（1）
最佳情况下的空间和时间复杂度是 O（1）。当流具有连续的整数（递增或递减）时，会发生这种最佳情况
,您的解决方案需要O（N）空间来保存数组和总和段树，并且需要O（N）时间来初始化它们；然后是两个查询的O（1）和O（log²N）。很显然，如果要查询很多，从长远来看，要跟踪“看到”的数字，您不能做得比O（N）空间更好。
但是，不同的数据结构可以改善查询时间。这是三个想法：
初始化树以包含从1到N的每个数字；这可以在O（N）时间内通过从叶子上盖起树来完成；叶子具有所有奇数，然后它们由2 mod 4的所有数字连接，然后由4 mod 8的数字连接，依此类推。该树占用O（N）空间。
processNext是通过在O（log N）时间中从树中删除数字来实现的。getSmallestNotSeen通过在O（log N）时间中找到最左边的节点来实现。如果多次调用getSmallestNotSeen，这是一个改进，但是如果很少调用getSmallestNotSeen，则您的解决方案会更好，因为它在O（1）中而不是在O（1）中执行processNext登录N）。
按顺序初始化一个包含数字1到N的双向链接列表，并创建一个大小为N的数组，其中包含指向每个节点的指针。这需要O（N）空间，并且需要O（N）时间。初始化一个变量，将缓存的最小值设为1。
processNext。如果删除的节点没有前任节点，则将缓存的最小值更新为后继节点保留的值。这是O（1）时间。getSmallestNotSeen是通过以O（1）时间返回缓存的最小值来实现的。这也是一种改进，尽管所涉及的常数可能更高，但渐近严格地更好。拥有大小为N的数组以及大小为N的双向链接列表的开销很大。
其他解决方案的时间要求主要取决于它们的初始化阶段，这需要O（N）时间。另一方面，初始化一个空的哈希集是O（1）。和以前一样，我们还初始化一个将当前最小值保持为1的变量。
processNext通过在O（1）摊销时间内将数字插入集合中来实现。getSmallestNotSeen通过将当前最小值递增直到不再存在于集合中来进行更新，然后将其返回。哈希集的成员资格测试为O（1），所有查询的增量数受调用processNext的次数限制，所以这也是O（1）的摊销时间。渐近而言，此解决方案花费O（1）时间进行初始化和查询，并且使用O（min（Q，N））空间，其中Q是查询数，而其他解决方案无论如何都使用O（N）空间
我认为证明O（min（Q，N））空间是渐近最优的应该是很直接的，因此哈希集被证明是最佳选择。功劳归于Dave，用于将哈希集与当前最小变量组合在一起，以在O（1）的摊销时间内完成getSmallestNotSeen。