找到列表中不存在的最小整数

Question

我的一位同事使用的一个有趣的访谈问题:

假设您有一个非常长的未排序的无符号64位整数列表.您如何找到列表中未出现的最小非负整数？

后续行动:现在已经提出了通过排序的明显解决方案,你能比O(n log n)更快地完成吗？

FOLLOW-UP:您的算法必须在具有1GB内存的计算机上运行

澄清:列表在RAM中,但它可能会消耗大量的内容.您将提前获得列表的大小,例如N.

Answer 1

如果数据结构可以就地变异并支持随机访问,那么您可以在O(N)时间和O(1)额外空间中进行.只需按顺序遍历数组,并为每个索引将索引处的值写入value指定的索引,递归地将该位置的任何值放到其位置并丢弃值> N.然后再次遍历数组查找该点其中value与索引不匹配 - 这是不在数组中的最小值.这导致最多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

Answer 2

这是一个O(N)使用O(N)空间的简单解决方案.我假设我们将输入列表限制为非负数,并且我们想要找到列表中不存在的第一个非负数.

1. 找到列表的长度; 让我们说它是N.
2. 分配一系列N布尔值,初始化为所有布尔值false.
3. 对于X列表中的每个数字,如果X小于N,则将X'th数组的元素设置为true.
4. 从索引开始扫描数组0,查找第一个元素false.如果你找到第一个false索引I,那么I就是答案.否则(即所有元素都是true),答案是N.

实际上," N布尔数组"可能被编码为表示为数组byte或int数组的"位图"或"位组" .这通常使用较少的空间(取决于编程语言)并允许false更快地完成第一次扫描.

这就是算法如何工作的原因.

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

上一段的替代方案是列表是来自的数字的排列0 .. N - 1.在这种情况下,步骤3将数组的所有元素设置为true,步骤4告诉我们第一个"缺失"数字是N.

该算法的计算复杂度O(N)具有相对较小的比例常数.它通过列表进行两次线性传递,或者如果已知列表长度,则只进行一次传递.没有必要表示将整个列表保存在内存中,因此算法的渐近内存使用正是表示布尔数组所需要的; 即O(N)比特.

(相比之下,依赖于内存中排序或分区的算法假设您可以在内存中表示整个列表.在提出问题的形式中,这将需要O(N)64位字.)

@Jorn评论说,步骤1到3是计数排序的变体.从某种意义上说,他是对的,但差异很大:

• 计数排序需要一组(至少)Xmax - Xmin计数器,其中Xmax列表中的最大数字是列表Xmin中的最小数字.每个计数器必须能够代表N个状态; 即,假设二进制表示,它必须具有整数类型(至少)ceiling(log2(N))位.
• 要确定数组大小,计数排序需要首先通过列表来确定Xmax和Xmin.
• 因此,最小的最坏情况空间要求是ceiling(log2(N)) * (Xmax - Xmin)比特.

相比之下,上面提出的算法只需要N在最差和最好的情况下使用位.

然而,这种分析导致直觉,即如果算法初始通过列表寻找零(并且如果需要则计算列表元素),如果它找到零,它将给出更快的答案,根本不使用空格.如果在列表中找到至少一个零的概率很高,那么绝对值得这样做.而这个额外的通行证并没有改变整体的复杂性.

编辑:我已经改变了算法的描述,使用"布尔数组",因为人们显然发现我使用位和位图的原始描述令人困惑.

Answer 3

由于OP现在已经指定原始列表保存在RAM中,并且计算机只有1GB的内存,我将会出局并预测答案为零.

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

相比之下,我今年被闪电击中的可能性是70万分之一.我被陨石击中的可能性大约是10万亿分之一.因此,由于天体过早死亡而不是零回答,我在科学期刊上写的可能性要高十倍.

Answer 4

正如在其他答案中指出的那样,您可以进行排序,然后直接扫描直到找到间隙.

您可以通过使用修改后的QuickSort将算法复杂度提高到O(N)并保留O(N)空间,从而消除不是包含间隙的潜在候选分区.

• 在第一个分区阶段,删除重复项.
• 分区完成后,查看下部分区中的项目数
• 此值是否等于用于创建分区的值？
  • 如果是这样,则意味着差距在更高的分区中.
    • 继续快速排序,忽略下部分区
  • 否则,间隙位于下部分区中
    • 继续快速排序,忽略更高的分区

这节省了大量计算.

Answer 5

由于数字都是64位长,我们可以对它们使用基数排序,即O(n).排序'em,然后扫描'直到找到你要找的东西.

如果最小数字为零,则向前扫描直到找到间隙.如果最小数字不为零,则答案为零.

Answer 6

为了说明O(N)思考的一个陷阱,这里有一个O(N)使用O(1)空间的算法.

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

print "no 64-bit integers are missing"

Answer 7

对于节省空间的方法,所有值都是不同的,您可以在空间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. inc count{j} 运用 j = (number - L)/k (if L < number < U)
4. 找到第一个h没有k个元素的region()
5. 如果count{h} = 1h是你的答案
6. 组 U = maximum value in region h L = minimum value in region h

这将运行O(log(N)*N).