algorithm - 如何从未排序的正整数流中找到最小的缺失正整数？

Question

可能重复：
查找不在列表中的最小整数

你有一个未排序的正整数流。从流中读取所有数字后，您必须确定流中缺少的最小正整数。

示例： 正整数流：6 7 8 9 1 2

答：3

正整数流：1 2 3 4 5

和：6

正整数流：12 87 899

答：1

我想在不采用任何额外数据结构的情况下解决问题。可能吗？

我被困在这个问题上。我在互联网上做了所有的研究，但是，没有运气。谁能帮忙。

Answer 1

您可以在读取数组时使用插入排序对数组进行排序（查看数据如何来自流，这应该很有效），然后遍历它。如果1缺少，这就是你的答案。如果它在那里，您可以迭代检查下一个整数是否是数组中的下一个数字，否则下一个整数是缺少的一个。

Answer 2

在满足以下两个约束的情况下，存在一种方法。该算法将扫描流两次并需要 256KB 内存。

1. 每个元素都小于或等于0xFFFFFFFF。
2. 流中的所有元素都是不同的。

下面展示了这个算法。

1. 分配一个数组：unsigned int bucket[2^16].
2. 扫描此流数据。如果当前数据是a，那么bucket[a>>16]++;
3. 扫描完这个流后，找到第一个值小于 的桶2^16。第一个丢失的无符号整数在这个桶中。设这个桶的索引是k，剩下的第一个无符号整数是n。然后k*(2^16) <= n < (k+1)*(2^16)。
4. 将所有存储桶的值重置为零。
5. 再次扫描此流数据。如果当前数据是a和k*(2^16) <= a < (k+1)*(2^16)，那么bucket[a&0xFFFF]++。
6. 再次扫描该流后，找到第一个值为 0 的存储桶。设这个桶的索引为h。

7. 这个答案n = k*(2^16) + h。

   注意：第三步的bucket[0]应该最多2^16 - 1而不是2^16因为无符号整数集合不包含0。

   　　ˊ