smallest-number-in-infinite-set

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have a set which contains all positive integers <code>[1, 2, 3, 4, 5, ...]</code>.

Implement the <code>SmallestInfiniteSet</code> class:

<ul>
	<li><code>SmallestInfiniteSet()</code> Initializes the SmallestInfiniteSet object to contain all positive integers.</li>
	<li><code>int popSmallest()</code> Removes and returns the smallest integer contained in the infinite set.</li>
	<li><code>void addBack(int num)</code> Adds a positive integer <code>num</code> back into the infinite set, if it is not already in the infinite set.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;SmallestInfiniteSet&quot;, &quot;addBack&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;addBack&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
 // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= num &lt;= 1000</code></li>
	<li>At most <code>1000</code> calls will be made in total to <code>popSmallest</code> and <code>addBack</code>.</li>
</ul>

Smallest Number in Infinite Set

First Missing Positive

first-missing-positive

缺失的第一个正数

Design

Hash Table

Ordered Set

Heap (Priority Queue)

现有一个包含所有正整数的集合 <code>[1, 2, 3, 4, 5, ...]</code> 。

实现 <code>SmallestInfiniteSet</code> 类：

<ul>
	<li><code>SmallestInfiniteSet()</code> 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。</li>
	<li><code>int popSmallest()</code> 移除 并返回该无限集中的最小整数。</li>
	<li><code>void addBack(int num)</code> 如果正整数 <code>num</code> 不 存在于无限集中，则将一个 <code>num</code> 添加 到该无限集中。</li>
</ul>

&nbsp;

示例：

<pre>
输入
["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 ，并将其从集合中移除。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= num &lt;= 1000</code></li>
	<li>最多调用 <code>popSmallest</code> 和 <code>addBack</code> 方法 共计 <code>1000</code> 次</li>
</ul>