30

这个问题是在亚马逊采访中被问到的——

给定一个正整数数组，您必须找到不能从数组中的数字之和形成的最小正整数。

例子：

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. 对数组进行排序
  2. 计算前缀和
  3. 遍历 sum 数组并检查下一个元素是否小于 1 大于 sum 即 A[j]<=(sum+1)。如果不是这样，那么答案将是sum+1

但这是 nlog(n) 解决方案。

面试官对此并不满意，并在不到 O(n log n) 的时间内提出了解决方案。

4

4 回答 4

52

有一个漂亮的算法可以在 O(n + Sort) 时间内解决这个问题，其中 Sort 是对输入数组进行排序所需的时间。

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

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

  • 如果当前数字大于您目前无法制作的最小数字，那么您知道您无法制作的最小数字 - 这是您记录的那个，您已经完成了。
  • 否则，当前数字小于或等于您无法制作的最小数字。声称你确实可以制作这个数字。现在，您知道使用数组的前 k 个元素（称为它candidate）无法生成的最小数字，现在正在查看 value A[k]。因此，该数字candidate - A[k]必须是您确实可以使用数组的前 k 个元素制作的某个数字，因为否则candidate - A[k]该数字将小于您据称无法使用数组中的前 k 个数字制作的最小数字。此外，您可以在candidate至candidate + A[k]（含）范围内创建任何数字，因为您可以从 1 至A[k]（含）范围内的任何数字开始，然后添加candidate - 1到它。因此，设置candidate为candidate + A[k]并递增k.

在伪代码中：

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]. 然后，设置candidate为 1。然后我们执行以下操作：

  • A[1] = 1, candidate= 1：
    • A[1] ≤ candidate，所以设candidate = candidate + A[1] = 2
  • A[2] = 2, candidate= 2：
    • A[2] ≤ candidate，所以设candidate = candidate + A[2] = 4
  • A[3] = 3, candidate= 4：
    • A[3] ≤ candidate，所以设candidate = candidate + A[3] = 7
  • A[4] = 4, candidate= 7：
    • A[4] ≤ candidate，所以设candidate = candidate + A[4] = 11
  • A[5] = 13, candidate= 11：
    • A[4] > candidate，所以返回candidate(11)。

所以答案是 11。

这里的运行时间是 O(n + Sort)，因为在排序之外，运行时间是 O(n)。您可以使用堆排序在 O(n log n) 时间内清楚地排序，如果您知道数字的一些上限，则可以使用基数排序在时间 O(n log U)（其中 U 是最大可能数）中排序。如果 U 是一个固定常数（例如 10 9），那么基数排序在 O(n) 时间内运行，而整个算法也在 O(n) 时间内运行。

希望这可以帮助！

于 2014-01-12T17:52:08.860 回答
9

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

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

b = b | b << k | 2^(k-1)

需要明确的是，第 i 个元素设置为 1 表示数字 i，并将| k第 k 个元素设置为 1。

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

  1. b=0
  2. 过程 4： b = b | b<<4 | 1000 = 1000
  3. 过程 13： b = b | b<<13 | 1000000000000 = 10001000000001000
  4. 过程 2： b = b | b<<2 | 10 = 1010101000000101010
  5. 过程 3： b = b | b<<3 | 100 = 1011111101000101111110
  6. 过程 1： b = b | b<<1 | 1 = 11111111111001111111111

第一个零：位置 11。

于 2014-01-12T20:50:42.987 回答
7

考虑区间 [2 i .. 2 i+1 - 1]中的所有整数。并假设所有低于 2 i的整数都可以由给定数组中的数字之和形成。还假设我们已经知道 C，它是小于 2 i的所有数字的总和。如果 C >= 2 i+1 - 1，则此区间中的每个数字都可以表示为给定数字的总和。否则，我们可以检查区间 [2 i .. C + 1] 是否包含给定数组中的任何数字。如果没有这样的数字，C + 1 就是我们搜索的。

这是一个算法的草图：

  1. 对于每个输入的数字，确定它属于哪个区间，并更新对应的 sum: S[int_log(x)] += x。
  2. 计算数组 S: 的前缀和foreach i: C[i] = C[i-1] + S[i]。
  3. 过滤数组 C 以仅保留值低于 2 的下一个幂的条目。
  4. 再次扫描输入数组并注意哪个区间 [2 i .. C + 1] 包含至少一个输入数：i = int_log(x) - 1; B[i] |= (x <= C[i] + 1).
  5. 找到在步骤 #3 中未过滤掉的第一个区间以及B[]在步骤 #4 中未设置的相应元素。

如果不清楚为什么我们可以应用第 3 步，这里就是证明。选择 2 i和 C 之间的任意一个数，然后依次减去 2 i以下的所有数以递减顺序。最终我们得到的数字要么小于最后一个减去的数字，要么为零。如果结果为零，只需将所有减去的数字相加，我们就有了所选数字的表示。如果结果非零且小于最后一个减数，则此结果也小于 2 i，所以它是“可表示的”，并且没有一个减去的数字用于表示它。当我们将这些减去的数字加回来时，我们就有了所选数字的表示。这也表明，我们可以通过直接跳转到 C 的 int_log 来一次跳过多个间隔，而不是一个一个过滤间隔。

时间复杂度由函数确定，函数int_log()是整数对数或数字中最高设置位的索引。如果我们的指令集包含整数对数或任何其等价物（计算前导零或浮点数技巧），则复杂度为 O(n)。否则，我们可以使用一些黑客技术int_log()在 O(log log U) 中实现并获得 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 * log M) 时间和 O(log M) 空间。其中 M 是数组中的最大数。读取所有数字需要相同的时间（在最坏的情况下，我们需要它们的每一位）。

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

于 2014-01-12T20:24:59.843 回答
0

如果您对数组进行排序，它将为您工作。计数排序本可以在 中完成O(n)，但如果您认为在一个实际较大的场景中，范围可能会非常高。

快速排序O(n*logn)将为您完成工作：

def smallestPositiveInteger(self, array): 
    candidate = 1
    n = len(array)
    array = sorted(array)
    for i in range(0, n):
        if array[i] <= candidate:
            candidate += array[i]
        else:
            break
    return candidate
于 2021-04-19T12:31:02.653 回答