不能由数组中的数之和形成的最小数

Question

这个问题是在亚马逊采访中问我的-

给定一个正整数数组，你必须找到一个最小的正整数，这个正整数不能由数组中的数字之和构成。

例子：

Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }

我做的是：

1. 对数组进行排序

但这是nlog（n）解

面试官对此不满意，在不到O（n logn）的时间内提出了解决方案。

Answer 1

考虑区间[2ⁱ...2^{i 1}-1]中的所有整数。并且假设所有低于2ⁱ的整数都可以由给定数组的数字之和形成。还假设我们已经知道C，它是低于2ⁱ的所有数字的和。如果C

下面是一个算法的草图：

1. 对于每个输入数字，确定其所属的区间，并更新相应的和：S[int_log（x）]=x
2. 计算数组S的前缀和：foreach i:C[i]=C[i-1]S[i]
3. 过滤数组C，只保留值小于下一次2次方的条目
4. 再次扫描输入数组，并注意哪个间隔[2ⁱ.c1]至少包含一个输入编号：i=int_log（x）-1；B[i]|=（x）

如果不清楚为什么我们可以应用第3步，下面是证据。选择2i和C之间的任何数字，然后按降序从中依次减去2i以下的所有数字。最终我们得到的要么是比最后一个减法数少的数，要么是零。如果结果为零，只需将所有减去的数字相加，我们就得到了所选数字的表示形式。如果结果为非零且小于最后一个减去的数字，则该结果也小于2，因此它是“可表示的”，且所有减去的数字均不用于其表示。当我们把这些减去的数字加回去时，我们得到了所选数字的表示形式。这也表明，我们可以直接跳到C的int_log，一次跳过几个间隔，而不是一个接一个地过滤间隔。

时间复杂度由函数int_log（）决定，它是整数对数或数字中最高集位的索引。如果我们的指令集包含整数对数或其任何等价物（计数前导零，或使用浮点数的技巧），则复杂度为O（n）。否则我们可以使用一些位黑客在O（log log U）中实现int_log（）并获得O（n*log log U）时间复杂度。（这里U是数组中最大的数字）。

如果第1步（除了更新和）还将更新给定范围内的最小值，则不再需要第4步。我们可以将C[i]与min[i 1]进行比较。这意味着我们只需要单遍输入数组。或者我们可以将此算法应用于数字流，而不是数组。

几个例子：

Input:       [ 4 13  2  3  1]    [ 1  2  3  9]    [ 1  1  2  9]
int_log:       2  3  1  1  0       0  1  1  3       0  0  1  3

int_log:     0  1  2  3          0  1  2  3       0  1  2  3
S:           1  5  4 13          1  5  0  9       2  2  0  9
C:           1  6 10 23          1  6  6 15       2  4  4 13
filtered(C): n  n  n  n          n  n  n  n       n  n  n  n
number in
[2^i..C+1]:  2  4  -             2  -  -          2  -  -
C+1:              11                7                5

对于多精度输入数，这种方法需要O（n*logm）时间和O（logm）空间。其中M是数组中的最大数。读取所有数字需要同样的时间（最糟糕的情况下，我们需要每一个数字）。

尽管如此，这个结果可能会被改进为O（n*logr），其中R是这个算法找到的值（实际上是它的输出敏感变量）。这种优化所需的唯一修改不是一次处理整数，而是逐位处理：第一次通过处理每个数字的低阶位（如位0..63），第二次通过-下一个位（如64..127），等等。在找到结果后，我们可以忽略所有高阶位。此外，这将空间需求减少到O（K）个数，其中K是机器字中的位数。

Answer 2

使用位向量在线性时间内完成此操作。

从空位向量b开始。然后对数组中的每个元素k执行以下操作：

b=b | b

为了清楚起见，第i个元素被设置为1来表示数字i，而|k将第k个元素设置为1。

处理完数组后，b中第一个零的索引就是你的答案（从右边开始计算，从1开始）。

1. b=0

第一个零：位置11。

Answer 3

时间O（n Sort）中有一个很好的算法可以解决这个问题，其中Sort是对输入数组进行排序所需的时间。

该算法的思想是对数组进行排序，然后问以下问题：使用数组的前k个元素不能生成的最小正整数是什么？然后从左到右向前扫描数组，更新这个问题的答案，直到找到无法生成的最小数字。

下面是它的工作原理。最初，最小的数字是1。然后，从左到右，执行以下操作：

• 如果当前的数字大于目前为止你不能生成的最小数字，那么你知道你不能生成的最小数字——这就是你记录的数字，你就完成了

在伪代码中：

Sort(A)
candidate = 1
for i from 1 to length(A):
   if A[i] > candidate: return candidate
   else: candidate = candidate + A[i]
return candidate

下面是对[4, 13, 2, 1, 3]的测试。对数组进行排序以获得[1, 2, 3, 4, 13]。然后，将候选设置为1。然后执行以下操作：

• A[1]=1，候选=1：
  • A[1]≤候选，所以设置候选=候选A[1]=2
  • A[2]≤ <代码>候选者，因此设置候选者=候选者A[2]=4
  • A[3]≤候选，所以设置候选=候选A[3]=7
  • A[4]≤ <代码>候选人，因此设置候选人=候选人A[4]=11
  • A[4]

  所以答案是11。

  这里的运行时是O（n Sort），因为在排序之外，运行时是O（n）。你可以使用heapsort在O（n logn）时间内清晰地排序，如果你知道一些数字的上限，你可以使用基数排序在O（n logu）时间内排序（U是最大可能的数字）。如果U是一个固定常数（例如，10⁹），那么基数排序在时间O（n）中运行，整个算法也在时间O（n）中运行。

  希望这有帮助！