无法从数组中的数字之和形成的最小数字

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

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

采访者对此并不满意,并在不到O(n log n)时间内提出解决方案.

Answer 1

在时间O(n + Sort)中有一个很好的算法来解决这个问题,其中Sort是对输入数组进行排序所需的时间.

算法背后的想法是对数组进行排序,然后提出以下问题:使用数组的前k个元素,你无法做出的最小正整数是多少？然后,您从左向右扫描阵列,更新您对此问题的答案,直到找到您无法制作的最小数字.

这是它的工作原理.最初,您不能做的最小数字是1.然后,从左到右,执行以下操作:

• 如果当前的数字大于你目前无法达到的最小数字,那么你就知道你不能做出的最小数字 - 这是你记录的数字,而你已经完成了.
• 否则,当前数字小于或等于您无法生成的最小数字.声称你可以确实这个数字.现在,您知道使用数组的前k个元素(称之为candidate)无法使用的最小数字,现在正在查看值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).您可以使用heapsort清楚地在O(n log n)时间内进行排序,如果您知道数字的某些上限,则可以使用基数排序按时间排序O(n log U)(其中U是最大可能数).如果U是固定常数(例如,10 ⁹),则基数排序在时间O(n)中运行,然后整个算法也在时间O(n)中运行.

希望这可以帮助!

Answer 2

使用bitvectors在线性时间内完成此操作.

从空位向量开始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.

Answer 3

考虑区间[2 ⁱ .. 2 ^{i + 1} - 1]中的所有整数.并且假设所有低于2 ^i的整数可以由给定数组的数字之和形成.还假设我们已经知道C,它是低于2 ⁱ的所有数字的总和.如果C> = 2 ^{i + 1} - 1,则该间隔中的每个数字可以表示为给定数字的总和.否则我们可以检查interval [2 ⁱ .. C + 1]是否包含给定数组中的任何数字.如果没有这样的号码,我们搜索的是C + 1.

这是一个算法草图:

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

如果不清楚为什么我们可以应用第3步,这是证据.选择2 ⁱ和C 之间的任意数字,然后按顺序从中减去2 ⁱ以下的所有数字.最终我们得到的数字少于最后一个减去的数字或零.如果结果为零,只需将所有减去的数字加在一起,我们就可以得到所选数字的表示.如果结果为非零且小于最后一个减去的数字,则该结果也小于2 ⁱ,因此它是"可表示的",并且没有一个减去的数字用于其表示.当我们添加这些减去的数字时,我们有所选数字的表示.这也表明,不是逐个过滤间隔,我们可以通过直接跳转到C的int_log来一次跳过几个间隔.

时间复杂度由函数确定,函数int_log()是整数对数或数字中最高设置位的索引.如果我们的指令集包含整数对数或其任何等价(计数前导零或具有浮点数的技巧),则复杂度为O(n).否则,我们可以使用一些黑客攻击来int_log()在O(日志日志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是机器字中的位数.