在一个列表中找到最小的未出现的整数

Question

在一个列表中找到最小的未出现的整数

arraysalgorithm

91

我同事在面试中提出了一个有趣的问题：

假设你被给予一个未排序的、非常长的无符号64位整数列表。你如何找到列表中不存在的最小的非负整数？

后续问题：既然已经提出了排序的显而易见的解决方案，你能否比O(n log n)更快地完成任务？

后续问题：你的算法必须在计算机上运行，例如1GB的内存。

澄清：这个列表在RAM中，尽管它可能占用大量内存。你预先知道列表的大小N。

- PeterAllenWebb

6

考虑到你谈论的是一个无符号整数，我认为你可以省略掉“非负”的部分，以使表述更加简明。 - KevenDenen

4

问题很基础，除非我完全错了，但是正如其他人所提到的，有些需要问的问题或者应该说明的假设。 - James Black

8

这是一个例子，其中说“O(n)”并不意味着太多。即使您将2^64位数组存储在复活节岛的黏土片上，并通过鸽子邮递员访问它，该算法仍然是O（n）。 - I. J. Kennedy

6

在面试中更改内存要求，这是一个非常好的面试问题。;-) - Chris Ballance

1

我认为很有趣的是所有答案都采用了相同的通用解决方案（对数组进行排序并找到打破序列的第一个值），但它们都使用了不同的排序方法（修改版快速排序，基数排序等）。被接受的答案相当于一种计数排序，它会丢弃超过N的元素。 - Joren

显示剩余10条评论

28个回答

91

这里有一个简单的 O(N) 解法，使用 O(N) 空间。假设我们将输入列表限制为非负数，并且要找到第一个不在列表中的非负数。

求出列表的长度，假设为 N。
分配一个包含 N 个布尔值的数组，初始化为全部为 false。
对于列表中的每个数字 X，如果 X 小于 N，则将数组的第 X 个元素设置为 true。
从索引 0 开始扫描数组，查找第一个为 false 的元素。如果您在索引 I 处找到第一个 false，则 I 是答案。否则（即当所有元素都为 true 时），答案是 N。

实际上，"包含 N 个布尔值的数组" 可能会被编码为作为 byte 或 int 数组表示的 "位图" 或 "bitset"。这通常使用更少的空间（取决于编程语言），并允许更快地扫描第一个 false。

这就是算法的工作原理和原因。

假设列表中的 N 个数字不是不同的，或者其中一个或多个大于 N。这意味着在范围 0 .. N - 1 中必须至少有一个数字不在列表中。因此，查找最小缺失数的问题必须减少到查找最小缺失数 小于 N 的问题。这意味着我们不需要跟踪大于或等于 N 的数字……因为它们不会是答案。

与前一段相反的是，列表是从 0 .. N - 1 中数字的排列。在这种情况下，步骤 3 将数组的所有元素设置为 true，并且步骤 4 告诉我们第一个“缺失”的数字是 N。

该算法的计算复杂度为 O(N)，比例系数相对较小。它通过列表进行两次线性通行，或者如果已知列表长度则只需要一次通行。没有必要将整个列表保存在内存中，因此算法的渐进空间使用量仅为表示布尔值数组所需的量；即 O(N) 位。

< p>与基于内存排序或分区的算法不同，这种算法假定您可以在内存中表示整个列表。按照问题的形式，这将需要O（N） 64位字）。

@Jorn指出，步骤1到3是计数排序的一个变体。从某种意义上说，他是对的，但差异很大：

计数排序需要一个包含（至少）Xmax-Xmin 个计数器的数组，其中Xmax 是列表中最大的数字，而 Xmin 是列表中最小的数字。每个计数器必须能够表示N个状态；即，假设使用二进制表示，它必须具有（至少） ceiling(log2(N))位的整数类型。
要确定数组大小，计数排序需要通过列表进行初始遍历，以确定Xmax 和 Xmin 。
因此，最小的最坏空间要求为 ceiling(log2(N)) * (Xmax-Xmin)位。

相比之下，上面展示的算法在最坏情况和最佳情况下仅需要N 位。

然而，这种分析使人产生一种直觉，即如果算法通过列表进行初始遍历以查找零（如果需要，计算列表元素），则在找到零时不使用任何空间即可更快地给出答案。如果有很大的可能性在列表中至少找到一个零，则绝对值得这样做。这个额外的遍历不会改变总体复杂度。

编辑：我已更改算法描述，以使用“布尔数组”，因为显然有人发现我最初使用位和位图的描述令人困惑。

- Stephen C

3

如果第三步得到了一个所有位都被设置为1的位图，那么列表中包含从0到N-1的每个值。这意味着列表中最小的非负整数是N。如果列表中存在任何介于0和N-1之间的未出现的值，则相应的位将不会被设置。因此，最小的这样的值即为答案。 - divegeek

4

在你的例子中，列表将包含300个元素。这意味着如果有任何“缺失”的值，它必须小于300。运行算法时，我们将创建一个具有300个插槽的位字段，然后重复设置插槽1、2和3中的位，使所有其他插槽——0和4到299——保持清晰。扫描位字段时，我们会发现插槽0的标志未设置，因此我们会知道0是答案。 - divegeek

4

请注意，这个算法可能更容易理解，如果不使用位运算：例如，“创建一个大小为N的布尔数组”等。一旦您以这种方式理解了它，转换成位运算版本在概念上就很容易了。 - Jon Skeet

2

在提供抽象解决方案时，使用最简单的概念方式，不要过度特化。您的解决方案需要使用一个（抽象）布尔数组，所以称其为布尔数组。无论您是通过bool []还是位图来实现该数组，与通用解决方案无关。 - Joren

2

我认为这个解决方案最好的描述是“使用一个计数排序，忽略掉大于N的元素，然后从开头开始进行线性搜索，找到第一个缺失的元素。” - Joren

显示剩余13条评论

14

由于OP现在已经指定原始列表保存在RAM中，并且计算机只有1GB的内存，我要冒险预测答案是零。

1GB的RAM意味着列表最多可以有134,217,728个数字。但是有2⁶⁴ = 18,446,744,073,709,551,616个可能的数字。因此，零在列表中的概率为137,438,953,472分之1。

相比之下，我今年被闪电击中的几率是70万分之一。而我被陨石击中的几率约为10万亿分之一。因此，我因天体物体而死亡并因此被写入科学期刊的几率大约是答案不为零的十倍。

- Barry Brown

11

如果这些值是均匀分布且随机选择的，那么你的计算才成立。但这些值也可能是顺序生成的，这时候情况就不一样了。 - divegeek

1

当然，你是正确的。但我一直在优化常见情况。 :) - Barry Brown

10

那么，如果回答这个问题，面试者被选中的几率有多大？ - Amarghosh

6

这个问题并没有指明这些数字是均匀随机选择的。它们是由出题人选择的。鉴于此，0出现在列表中的概率要比1/137,438,953,472（2的38次方）大得多，甚至可能大于1/2。:-) - ShreevatsaR

8

那个问题的答案也是零。 - PeterAllenWebb

显示剩余2条评论

10

正如其他答案所指出的，您可以进行排序，然后简单地扫描直到找到一个间隙。

你可以通过使用改进的快速排序算法将算法复杂度优化为O(N)，同时保持O(N)的空间利用率，其中你会消除那些不可能包含间隙的分区。

在第一阶段分区时，删除重复项。
完成分区后，查看较低分区中的项目数
这个值是否等于创建分区时使用的值？
- 如果是，则意味着间隙在较高的分区中。
  - 继续使用快速排序算法，忽略较低的分区
- 否则，间隙在较低的分区中
  - 继续使用快速排序算法，忽略较高的分区

这样可以节省大量计算。

- cdiggins

这很不错。它会假设您可以在小于线性时间内计算分区的长度，如果将其与分区数组一起存储，则可以完成此操作。它还假定原始列表保存在RAM中。 - Barry Brown

2

如果您知道列表的长度，您也可以剔除任何大于len(list)的值。根据鸽巢原理，任何“空洞”都必须小于len(list)。 - divegeek

1

我不认为这是O(n)的...首先，我不确定在列表完全排序之前是否可以删除重复项。其次，虽然您可以保证每次迭代丢弃一半的搜索空间（因为您已将其分成中点以下和中点以上），但您仍然需要多次通过依赖于n的数据（取决于n）。 - paxdiablo

1

paxdiablo：您可以使用位图方法构建仅具有唯一值的新列表，就像Stephen C所建议的那样。这将在O(n)时间和空间内运行。我不确定是否有比这更好的方法。 - Nic

8

为了说明“O(N)”思维的一个缺陷，这里有一个使用“O(1)”空间的“O(N)”算法的例子。

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

- I. J. Kennedy

1

Will 是正确的。这不是 O(n)，因为你实际上有两个循环，但其中一个是隐式的。确定一个值是否在列表中是一个 O(n) 的操作，并且你在 for 循环中做了 n 次。这使得它成为 O(n^2)。 - Nic

7

Nic，Will，这是O(n * N)的时间复杂度，其中n是列表的大小，N是域的大小（64位整数）。虽然N是一个巨大的数字，但它仍然是一个常数，因此按照所述问题的正式复杂度为O(n)。 - Ants Aasma

1

蚂蚁们，我同意这是O(nN)的时间复杂度，但N并不是一个常数。因为当算法找到答案时就会停止，外层循环完整迭代的次数等于答案本身，而答案又受列表大小的限制。所以，在这种情况下，O(Nn)就是O(n^2)。 - Will Harris

13

在一个包含N个元素的列表中查找一个数字显然是O(N)。我们要执行2^64次这样的操作。虽然非常大，但2^64是一个常数。因此，该算法的时间复杂度为C*O(N)，仍然是O(N)。 - I. J. Kennedy

3

我必须收回之前的声明；按最严格的定义，这个操作确实是O(n)。 - Nic

显示剩余6条评论

8

由于所有数字长度均为64位，我们可以使用基数排序，其时间复杂度为O(n)。对它们进行排序，然后扫描它们，直到找到你要的数字。

如果最小的数字是零，则向前扫描，直到找到空隙。如果最小的数字不是零，则答案为零。

- Barry Brown

是的，但基数排序的内存需求可能会非常高。 - PeterAllenWebb

1

基数排序在非常大的数据集上效果不好。但是分区和基数排序可能会起作用。 - DarthVader

5

为了实现占用空间较小的方法，并且所有值都是不同的，您可以使用空间复杂度为O(k)和时间复杂度为O(k*log(N)*N)的方法。它具有高效的空间利用率，没有数据移动，所有操作都是基本操作（加减）。

1.设置U=N;L=0。 2.首先将数字空间划分为k个区域。像这样:

- 0->(1/k)*(U-L) + L，0->(2/k)*(U-L) + L，0->(3/k)*(U-L) + L ... 0->(U-L) + L 3.找到每个区域中有多少个数字(count{i})。（N*k步） 4.找到第一个不满的区域(h)。这意味着count{h} < upper_limit{h}。（k步） 5.如果h-count{h-1}=1，则找到了答案。 6.设置U=count{h};L=count{h-1}。 7.返回第2步。

这可以通过使用哈希来改进（感谢Nic提供的思路）。

1.同上。 2.首先将数字空间划分为k个区域。像这样:

- L+(i/k)->L+(i+1/k)*(U-L) 3.使用j=(number-L)/k(如果L<number<U)来增加count{j}。 4.找到第一个没有k个元素的区域(h)。 5.如果count{h}=1，则找到了答案。 6.设置U=区域h中的最大值，L=区域h中的最小值。 7.返回第2步。

该算法的时间复杂度为O(log(N)*N)。

- Egon

这不是以O(log(N)*N)的时间运行，而是以O(N)的时间运行。你的答案是@cdiggins答案的概括，并且它以O(N)的时间运行，因为sum(1/k**i for i in range(ceil(log_k(n)))) <= 2。 - Lapinot

在每次迭代中，您需要遍历O(N)个数字，总共需要O(log_k(N))次迭代。因此，O(log_k(N)*N) == O(log(N)*N)。原始数字未排序/分桶，您需要遍历所有数字。 - Egon

但是，如果您将原始列表分成k个区域（每个区域的大小为n/k），则选择第一个未满的区域。因此，在下一次迭代中，您只需要考虑所选区域并将其分成k个新区域（每个区域的大小为n/k ** 2）等等。实际上，您不需要每次都迭代整个列表（否则分区有什么意义呢？）。 - Lapinot

你将数字空间进行分区，而不是对数字本身进行分区。否则，这根本无法在O(k)内存中运行且不修改原始数字。 - Egon

嗯，我现在明白了。实际上，我误解了你的算法（但如果你将数字分区，它也可以工作：你会得到O(k*n)时间和O(n/k)空间）。所以你的算法就像原地排序方法，但不会破坏任何东西，很有趣 :) - Lapinot

显示剩余2条评论

3

我会先将它们排序，然后按顺序遍历，直到找到一个空缺（包括零和第一个数字之间的空缺）。

就算法而言，可以使用以下算法：

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

当然，如果你的内存比CPU强大得多，你可以创建一个包含所有可能的64位值的位掩码，并为列表中的每个数字设置位。然后在该位掩码中查找第一个0位。这将使其成为时间复杂度为O(n)的操作，但在内存需求方面相当昂贵 :-)

我怀疑你无法改进O(n)，因为我看不到一种不需要至少查看每个数字的方法。

其算法大致如下：

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

- paxdiablo

从描述中看来，它似乎排除了0作为第一个元素，因为它是列表中不存在的最小值。但这只是我做出的一种假设，我可能是错的。 - James Black

我的想法是，如果排序后的序列是4、5、6，那么0将是列表中不存在的最小值。 - paxdiablo

我预计2、3、5的答案应该是4，但是我可能错了。 - James Black

这是一个应该由提问者回答的问题。搜索空间是“所有64位无符号整数”还是“列表中最低和最高数字之间的所有数字”？ - paxdiablo

@paxdiablo 这个问题应该被完全按字面意思理解。即列表中没有出现过的最小整数。从理论上讲，列表可能包含所有2^64个整数，但是让我们假设这永远不会发生，因为它需要大量的内存。 - PeterAllenWebb

显示剩余3条评论

2

我们可以使用哈希表来存储这些数字。当所有数字处理完毕后，从0开始计数直到找到最小值。一个合理的哈希函数将会在常数时间内进行哈希和存储，并在常数时间内检索。

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

如果数组中有n个元素，且这些元素是{0, 1, ... n-1}，那么最坏情况下答案将在n处得出，但时间复杂度仍为O(n)。

- Milind C

2

对列表进行排序，查看第一个和第二个元素，并开始向上移动直到出现间隔。

- James Black

取决于你的定义，不在列表中。 - James Black

@PeterAllenWebb - 会有的，但是这些数字是随机排列还是已排序？ - James Black

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ants Aasma · Accepted Answer

如果数据结构可以原地改变并支持随机访问，则可以在O（N）时间和O（1）额外空间内完成。只需按顺序遍历数组，并为每个索引将该索引处的值写入到指定值的索引位置，递归地将该位置的任何值放置到其位置并丢弃大于N的值。然后再次遍历数组，查找值与索引不匹配的位置-那就是数组中最小的值。这最多需要3N次比较，仅使用少量值的临时空间。

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N