我有一段时间有一个有趣的面试经历 . 问题开始很简单:
Q1:我们有一个包含数字1,2,3,...,100的包 . 每个数字只出现一次,因此有100个数字 . 现在从包里随机挑出一个号码 . 找到丢失的号码 .
当然,我之前听过这个采访问题,所以我很快回答了以下问题:
A1:嗯,数字1 2 3 ... N的总和是(N 1)(N / 2)(参见维基百科:算术系列之和) . 对于N = 100,总和是5050.因此,如果包中存在所有数字,则总和将精确为5050.由于缺少一个数字,总和将小于此数,并且差异是该数字 . 因此我们可以在O(N)时间和O(1)空间中找到丢失的数字 .
在这一点上,我认为我做得很好,但突然间这个问题发生了意想不到的转变:
Q2:这是正确的,但现在如果缺少两个数字你会怎么做?
我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题 . 面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一次传递中收集了一些信息后再进行第二次传递,但我真的只是在拍摄在黑暗中而不是实际上有一条清晰的解决方案 .
面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法 . 在这一点上,我有点不高兴(因为事先不知道答案),并询问这是否是一般(读取:“有用”)编程技术,或者它只是一个技巧/问题答案 .
面试官的回答让我感到惊讶:你可以推广这项技术,找到3个缺失的数字 . 实际上,您可以将其概括为找到k个缺失的数字 .
Qk:如果 Baggage 中缺少k个号码,您会如何有效地找到它?
这是几个月前的事情,我仍然无法在时间下限,因为我们必须扫描所有数字至少一次,但采访者坚持解决技术的时间和空间复杂性(减去 O(N)
时间输入扫描)以k而不是N定义 .
所以这里的问题很简单:
-
你会如何解决 Q2 ?
-
你会如何解决 Q3 ?
-
你会如何解决 Qk ?
澄清
-
一般来说,1..N中有N个数字,而不仅仅是1..100 .
-
我不是在寻找明显的基于集合的解决方案,例如使用bit set,将每个数字的存在/不存在编码指定位的值,因此在额外空间中使用
O(N)
位 . 我们无法承受与N成比例的任何额外空间 . -
我也不是在寻找明显的排序优先方法 . 这个和基于集合的方法在一次采访中值得一提(它们易于实现,并且取决于N,可能非常实用) . 我正在寻找圣杯解决方案(可能实现也可能不实用,但仍具有所需的渐近特征) .
所以,当然你必须扫描 O(N)
中的输入,但是你只能捕获少量信息(用k而不是N来定义),然后必须以某种方式找到k个缺失的数字 .
30 回答
这可能听起来很愚蠢,但是,在提交给您的第一个问题中,您必须看到包中的所有剩余数字才能实际添加它们以使用该等式找到丢失的数字 .
所以,既然你可以看到所有数字,只需查找缺少的数字 . 当缺少两个数字时也是如此 . 我觉得很简单 . 当你看到袋子里剩下的数字时,没有必要使用方程式 .
你会通过阅读Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers的几页来找到它 . It shows exactly the generalization you are looking for . 这可能是你的面试官阅读的内容以及他提出这些问题的原因 .
现在,如果只有人们会开始删除被Muthukrishnan治疗所包含或取代的答案,并使这个文本更容易找到 . :)
Also see sdcvvc's directly related answer ,其中还包括伪代码(欢呼!不需要阅读那些棘手的数学公式:))(谢谢,干得好!) .
另一种方法是使用残差图过滤 .
假设我们有数字1到4而缺少3 . 二进制表示如下,
1 = 001b,2 = 010b,3 = 011b,4 = 100b
我可以创建如下的流程图 .
请注意,流程图包含x个节点,而x是位数 . 并且最大边数是(2 * x)-2 .
因此对于32位整数,它将占用O(32)空间或O(1)空间 .
现在如果我从1,2,4开始删除每个数字的容量,那么我剩下一个残差图 .
最后我将运行如下的循环,
现在结果是
result
包含不丢失的数字(误报) . 但 k <= (size of the result) <= n 时有k
缺少元素 .我将最后一次通过给定的列表来标记结果是否丢失 .
所以时间复杂度将是O(n) .
最后,通过获取节点
00
,01
,11
,10
而不仅仅是0
和1
,可以减少误报数(以及所需空间) .如果你有两个列表的总和,你可以解决Q2两个清单的产品 .
(l1是原始的,l2是修改后的列表)
我们可以对此进行优化,因为算术系列的总和是第一个和最后一个项的平均值的n倍:
现在我们知道(如果a和b是删除的数字):
所以我们可以重新安排到:
并且乘出:
并重新排列,因此右侧为零:
然后我们可以用二次公式求解:
示例Python 3代码:
我不知道sqrt,reduce和sum函数的复杂性,所以我无法弄清楚这个解决方案的复杂性(如果有人知道请在下面评论 . )
我认为这可以在没有任何复杂的数学方程和理论的情况下完成 . 以下是现场和O(2n)时间复杂度解决方案的建议:
输入形式假设:
bag中的数字数量= n
缺失数字的数量= k
袋子中的数字由长度为n的数组表示
算法的输入数组的长度= n
数组中缺少的条目(从包中取出的数字)将替换为数组中第一个元素的值 .
例如 . 最初的包看起来像[2,9,3,7,8,6,4,5,1,10] . 如果取出4,则值4将变为2(数组的第一个元素) . 因此在拿出4个包之后会看起来像[2,9,3,7,8,6,2,5,1,10]
此解决方案的关键是通过在遍历数组时取消该INDEX处的值来标记访问数字的INDEX .
要解决2(和3)缺失数字问题,您可以修改quickselect,它平均在
O(n)
中运行,并且如果分区就地完成则使用常量内存 .将关于随机数据集
p
的集合划分为分区l
(包含小于数据透视表的数字)和r
(包含大于数据透视表的数字) .通过将透视值与每个分区的大小进行比较,确定2个缺失数字所在的分区(
p - 1 - count(l) = count of missing numbers in l
和n - count(r) - p = count of missing numbers in r
)a)如果每个分区缺少一个数字,则使用总和方法来查找每个缺失的数字 .
(1 + 2 + ... + (p-1)) - sum(l) = missing #1
和((p+1) + (p+2) ... + n) - sum(r) = missing #2
b)如果一个分区缺少两个数字且分区为空,则缺少的数字是
(p-1,p-2)
或(p+1,p+2)
,具体取决于哪个分区缺少数字 .如果一个分区缺少2个数字但不是空的,则递归到该分区 .
由于只有2个缺失的数字,此算法始终丢弃至少一个分区,因此它保留了quickselect的平均时间复杂度 . 类似地,如果缺少3个数字,则该算法还会在每次传递时丢弃至少一个分区(因为与2个缺失的数字一样,最多只有1个分区将包含多个缺失的数字) . 但是,当添加更多缺失数字时,我不确定性能会下降多少 .
这是一个不使用就地分区的实现,因此这个示例不满足空间要求,但它确实说明了算法的步骤:
Demo
我认为这可以概括为:
将S,M表示为算术系列和乘法之和的初始值 .
我应该考虑一个计算这个的公式,但这不是重点 . 无论如何,如果缺少一个数字,您已经提供了解决方案 . 但是,如果缺少两个数字,那么我们用S1和M1表示新的总数和总数,如下所示:
由于你知道S1,M1,M和S,上面的等式可以解决找到a和b,缺失的数字 .
现在缺少三个数字:
现在你的未知数是3,而你只有两个可以解决的方程式 .
您可以通过在对称性(组,数学语言)方面考虑它来激发解决方案 . 无论数字集的顺序如何,答案应该是相同的 . 如果您要使用
k
函数来帮助确定缺少的元素,您应该考虑具有该属性的函数:对称 . 函数s_1(x) = x_1 + x_2 + ... + x_n
是对称函数的一个例子,但还有其他更高程度的函数 . 特别要考虑 elementary symmetric functions . 2阶的基本对称函数是s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n
,即两个元素的所有乘积之和 . 类似地,对于3级和更高级的基本对称函数 . 它们显然是对称的 . 此外,事实证明它们是所有对称函数的构建块 .您可以通过注意
s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1))
来构建基本对称函数 . 进一步的想法应该说服你s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))
等等,所以它们可以在一次通过中计算 .我们如何判断数组中缺少哪些项目?想想多项式
(z-x_1)(z-x_2)...(z-x_n)
. 如果您输入任何数字x_i
,它将评估为0
. 扩展多项式,得到z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n
. 基本对称函数也出现在这里,这实在不足为奇,因为如果我们应用任何函数,多项式应该保持不变对根的排列 .因此,我们可以构建多项式并尝试将其考虑在内,以确定哪些数字不在集合中,正如其他人所提到的那样 .
最后,如果我们担心溢出大数字的内存(第n个对称多项式将是
100!
的顺序),我们可以进行这些计算mod p
,其中p
是一个大于100的素数 . 在这种情况下,我们评估多项式mod p
并找到当输入是集合中的数字时,它再次计算为0
,当输入是不在集合中的数字时,它计算为非零值 . 然而,正如其他人所指出的那样,为了从多项式中获取取决于k
的值,而不是N
,我们必须考虑多项式mod p
.不确定,如果它是最有效的解决方案,但我会遍历所有条目,并使用bitset记住,设置哪些数字,然后测试0位 .
我喜欢简单的解决方案 - 我甚至相信,它可能比计算总和或平方和等更快 .
对于Q2,这是一个比其他解决方案效率低一点的解决方案,但仍然具有O(N)运行时并且需要O(k)空间 .
想法是运行原始算法两次 . 在第一个中,您将得到一个缺失的总数,它为您提供缺失数字的上限 . 我们把这个号码称为
N
. 你知道缺少的两个数字总和为N
,所以第一个数字只能在[1, floor((N-1)/2)]
区间内,而第二个数字将在[floor(N/2)+1,N-1]
中 .因此,您再次循环所有数字,丢弃第一个间隔中未包含的所有数字 . 那些是,你跟踪他们的总和 . 最后,你会知道其中一个缺失的两个数字,并且通过扩展来知道第二个数字 .
我有一种感觉,这种方法可以推广,并且可能在单次传递输入期间以“并行”方式运行多次搜索,但我还没弄清楚如何 .
基于数字总和的解决方案的问题是它们没有考虑存储和使用具有大指数的数字的成本......在实践中,为了使其适用于非常大的n,将使用大数字库 . 我们可以分析这些算法的空间利用率 .
我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度 .
存储:
所以
l_j \in \Theta(j log n)
使用的总存储空间:
\sum_{j=1}^k l_j \in \Theta(k^2 log n)
使用的空间:假设计算
a^j
需要ceil(log_2 j)
时间,总时间:使用的总时间:
\Theta(kn log n)
如果这个时间和空间令人满意,您可以使用简单的递归算法 . 设b!i是包中的第i个条目,n是删除前的数字,k是删除的数量 . 在Haskell语法中......
使用的存储:
O(k)
表示列表,O(log(n))
表示堆栈:O(k + log(n))
此算法更直观,具有相同的时间复杂度,并且占用的空间更少 .我不知道这是否有效,但我想建议这个解决方案 .
计算100个元素的xor
计算98个元素的xor(删除2个元素后)
现在(1的结果)XOR(2的结果)给出了两个缺失的n的xor i..e如果a和b是缺失的元素的XOR b
4.用你通常的和公式差值方法得到缺失的Nos的总和,让我们说diff是d .
现在运行一个循环来获得可能的对(p,q),它们都位于[1,100]并且总和为d .
当获得一对时,检查(3的结果)XOR p = q,如果是,我们就完成了 .
如果我错了,请纠正我,如果这是正确的,还要评论时间复杂性
可能这个算法可以用于问题1:
预先计算前100个整数的xor(val = 1 ^ 2 ^ 3 ^ 4 .... 100)
xor元素,因为它们不断来自输入流(val1 = val1 ^ next_input)
最终答案= val ^ val1
甚至更好:
事实上,该算法可以扩展为两个缺失的数字 . 第一步保持不变 . 当我们用两个缺少的数字调用GetValue时,结果将是
a1^a2
是两个缺失的数字 . 让我们说val = a1^a2
现在从val中筛出a1和a2,我们取val中的任何设置位 . 假设
ith
位在val中设置 . 这意味着a1和a2在ith
位位置具有不同的奇偶校验 . 现在我们对原始数组进行另一次迭代并保留两个xor值 . 一个用于具有第i位设置的数字,而另一个用于没有第i位设置的数字 . 我们现在有两个数字桶,它保证a1 and a2
将位于不同的桶中 . 现在重复我们在每个桶上找到一个缺少元素所做的相同操作 .我相信我有一个
O(k)
时间和O(log(k))
空间算法,假设您有floor(x)
和log2(x)
函数可用于任意大整数:你有一个
k
位长的整数(因此是log8(k)
空格)你添加了x^2
,其中x是你找到的下一个数字包:s=1^2+2^2+...
这需要O(N)
时间(这对面试官来说不是问题) . 最后你得到j=floor(log2(s))
这是你正在寻找的最大数字 . 那么s=s-j
又你又做了以上事情:现在,您通常没有
2756
-bit整数的floor和log2函数,而是双精度函数 . 所以?简单地说,对于每2个字节(或1个,3个或4个),您可以使用这些函数来获得所需的数字,但这会为时间复杂度增加一个O(N)
因子我们大部分时间都可以在 O(log n) 做 Q1 and Q2 .
假设我们的
memory chip
由n
数字test tubes
组成 . 并且在试管中的数字x
由化学液体x
milliliter
表示 .假设我们的处理器是
laser light
. 当我们点亮激光时,它会垂直穿过所有管子的长度 . 每当它通过化学液体时,光度就会减少1
. 并且以一定毫升的标记传递光线是O(1)
的操作 .现在,如果我们将激光照射在试管中间并获得亮度输出
等于预先计算的值(在没有数字丢失时计算),然后缺失的数字大于
n/2
.如果我们的输出较小,则至少有一个缺失的数字小于
n/2
. 我们还可以检查亮度是否减少1
或2
. 如果减少了1
那么一个缺失的数字小于n/2
而另一个大于n/2
. 如果减少2
,则两个数字都小于n/2
.我们可以一次又一次地重复上述过程,缩小我们的问题域 . 在每一步中,我们将域缩小一半 . 最后我们可以得到我们的结果 .
并行算法值得一提(因为它们很有趣),
按一些并行算法排序,例如,并行合并可以在
O(log^3 n)
时间完成 . 然后可以在O(log n)
时间通过二进制搜索找到丢失的数字 .理论上,如果我们有
n
处理器,那么每个进程都可以检查其中一个输入并设置一些标识数字的标志(方便地在数组中) . 在下一步中,每个进程都可以检查每个标志,最后输出未标记的数字 . 整个过程需要O(1)
时间 . 它还有额外的O(n)
空间/内存要求 .注意,那是 two parallel algorithms provided above may need additional space as mentioned in the comment .
我会采用不同的方法解决这个问题,然后向访调员探讨他正试图解决的更大问题的更多细节 . 根据问题及其周围的要求,明显的基于集合的解决方案可能是正确的,并且生成列表和后续选择方法可能不是 .
例如,可能是面试官要发送
n
消息并且需要知道没有得到回复的k
并且需要在n-k
回复到达后尽可能少的挂钟时间知道它 . 让's also say that the message channel'的性质是这样的,即使在全部运行,也有足够的时间在消息之间进行一些处理,而不会影响在最后一个回复到达之后产生最终结果所需的时间 . 可以将该时间用于将每个发送的消息的一些识别方面插入到集合中并在每个相应的答复到达时将其删除 . 一旦最后一个回复到达,唯一要做的就是从集合中删除它的标识符,在典型的实现中需要O(log k+1)
. 之后,该集合包含k
缺少元素的列表,并且没有其他处理要做 .这当然不是批量处理预生成数字包的最快方法,因为整个事情运行
O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k))
. 但它确实适用于k
的任何值(即使它未提前知道),并且在上面的示例中,它以最小化最关键区间的方式应用 .你能检查一下这个号码是否存在吗?如果是,您可以尝试这样做:
如果缺少的数字是
x
和y
那么:所以你检查从
1
到max(x)
的范围并找到数字这是一个使用k位额外存储的解决方案,没有任何巧妙的技巧,只是直截了当 . 执行时间O(n),额外空间O(k) . 只是为了证明这可以在不阅读解决方案的情况下解决第一个还是天才:
等一下 . 正如问题所述,包里有100个号码 . 无论k有多大,问题都可以在恒定时间内解决,因为你可以在一个循环的最多100-k次迭代中使用一个集合并从集合中删除数字 . 100是不变的 . 剩下的数字是你的答案 .
如果我们将解决方案推广到从1到N的数字,除了N不是常数之外什么都没有变化,所以我们处于O(N-k)= O(N)时间 . 例如,如果我们使用位集,我们在O(N)时间内将位设置为1,迭代数字,将位设置为0(O(Nk)= O(N))然后我们有答案 .
在我看来,面试官问你如何在O(k)时间而不是O(N)时间打印出最终集的内容 . 显然,通过位设置,您必须遍历所有N位以确定是否应该打印该数字 . 但是,如果更改实现集的方式,则可以以k次迭代打印出数字 . 这是通过将数字放入要存储在哈希集和双向链表中的对象来完成的 . 从哈希集中删除对象时,也会从列表中删除它 . 答案将保留在现在长度为k的列表中 .
可能的解决方案:
以下是Dimitris Andreou's link的摘要 .
记住i次幂的总和,其中i = 1,2,...,k . 这减少了求解方程组的问题
a1 a2 ... ak = b1
a12 a22 ... ak2 = b2
...
a1k a2k ... akk = bk
使用Newton's identities,知道bi允许计算
c1 = a1 a2 ... ak
c2 = a1a2 a1a3 ... ak-1ak
...
ck = a1a2 ... ak
如果扩展多项式(x-a1)...(x-ak),系数将精确为c1,...,ck - 请参阅Viète's formulas . 由于每个多项式因子唯一(多项式的环是Euclidean domain),这意味着ai是唯一确定的,直到排列 .
这结束了一个证据,即记住功率足以恢复数字 . 对于常数k,这是一个很好的方法 .
然而,当k变化时,计算c1,...,ck的直接方法是非常昂贵的,因为例如ck是所有缺失数字的乘积,幅度为n!/(n-k)!为了克服这一点,执行computations in Zq field,其中q是素数,使得n <= q <2n - 它由Bertrand's postulate存在 . 证明不需要改变,因为公式仍然成立,并且多项式的因子分解仍然是唯一的 . 您还需要一种算法来对有限域进行分解,例如Berlekamp或Cantor-Zassenhaus .
常数k的高级伪代码:
计算给定数字的第i个幂
减去获得未知数的第i个幂的总和 . 称总和为bi .
使用牛顿的身份来计算bi的系数;叫他们ci . 基本上,c1 = b1; c2 =(c1b1-b2)/ 2;请参阅维基百科的确切公式
对多项式xk-c1xk-1 ... ck进行因子分解 .
多项式的根是所需的数字a1,...,ak .
对于变化的k,使用例如,找到素数n <= q <2n . 米勒 - 拉宾,并执行所有数字减少模数q的步骤 .
编辑:该答案的先前版本表明,在q为素数的情况下,代替Zq,可以使用特征2的有限域(q = 2 ^(log n)) . 事实并非如此,因为牛顿的公式需要按数字除以k .
我没有检查数学,但我怀疑计算
Σ(n^2)
在我们计算Σ(n)
的同一通道中将提供足够的信息以获得两个缺失的数字,如果有三个,则执行Σ(n^3)
,依此类推 .我们可以通过将数字本身和数字的平方相加来求解Q2 .
然后我们可以将问题减少到
其中
x
和y
是总和低于预期值的程度 .替代给了我们:
然后我们可以解决以确定我们缺少的数字 .
有一种通用的方法来推广像这样的流式算法 . 我们的想法是使用一点随机化来将'spread'元素转化为独立的子问题,我们的原始算法为我们解决了问题 . 该技术用于稀疏信号重建等 .
创建一个大小为
u = k^2
的数组a
.选择任何universal hash function,
h : {1,...,n} -> {1,...,u}
. (比如multiply-shift)对于
1, ..., n
中的每个i
增加a[h(i)] += i
对于输入流中的每个数字
x
,递减a[h(x)] -= x
.如果所有缺失的数字都被散列到不同的桶,则数组的非零元素现在将包含缺失的数字 .
根据通用散列函数的定义,将特定对发送到同一个桶的概率小于
1/u
. 由于大约有k^2/2
对,我们认为错误概率最多为k^2/2/u=1/2
. 也就是说,我们成功的概率至少为50%,如果我们增加u
,我们就会增加机会 .请注意,此算法需要
k^2 logn
位空间(每个数组桶需要logn
位 . )这匹配@Dimitris Andreou的答案所需的空间(特别是多项式因子分解的空间要求,也恰好是随机化的 . )此算法每次更新也有恒定的时间 . 而不是时间k
在幂和的情况下 .实际上,通过使用注释中描述的技巧,我们可以比功率和方法更有效 .
您可以尝试使用Bloom Filter . 将包中的每个数字插入到bloom中,然后遍历完整的1-k集,直到报告每个未找到的数字 . 这可能无法在所有情况下找到答案,但可能是一个足够好的解决方案 .
您可能需要澄清O(k)的含义 .
这是任意k的一个简单解决方案:对于你的数字集合中的每个v,累加2 ^ v的总和 . 最后,循环i从1到N.如果与2 ^ i按位和,则为零,则i丢失 . (或数字上,如果总和除以2 ^ i的平面是偶数 . 或
sum modulo 2^(i+1)) < 2^i
. )容易,对吗? O(N)时间,O(1)存储,并且它支持任意k .
除了你计算在真实计算机上的每个都需要O(N)空间的巨大数字 . 实际上,该解决方案与位向量相同 .
所以你可以聪明地计算总和和平方和和多维数据集的总和......直到v ^ k的总和,然后用花哨的数学来提取结果 . 但这些也是大数字,这引出了一个问题:我们在谈论什么样的抽象运作模式?在O(1)空间中适合多少,以及总结所需数量的数量需要多长时间?
正如@j_random_hacker指出的那样,这与Finding duplicates in O(n) time and O(1) space非常相似,我的答案也适用于此 .
假设"bag"由大小为
N - k
的基于1的数组A[]
表示,我们可以在O(N)
时间和O(k)
额外空间中求解Qk .首先,我们通过
k
元素扩展数组A[]
,使其现在的大小为N
. 这是O(k)
额外的空间 . 然后我们运行以下伪代码算法:第一个循环将
k
额外条目初始化为与数组中的第一个条目相同(这只是我们知道已经存在于数组中的一个方便的值 - 在此步骤之后,在初始数组中缺少任何条目扩展数组中仍然缺少N-k
) .第二个循环置换扩展数组,以便如果元素
x
至少存在一次,那么其中一个条目将位于A[x]
位置 .请注意,虽然它有一个嵌套循环,它仍然在
O(N)
时间运行 - 只有i
这样A[i] != i
才会发生交换,并且每个交换设置至少一个元素A[i] == i
,之前不是这样的 . 这意味着交换的总数(以及while
循环体的总执行次数)最多为N-1
.第三个循环打印数组
i
的那些未被值i
占用的索引 - 这意味着i
必定已丢失 .非常好的问题 . 我会为Qk使用一组差异 . 许多编程语言甚至都支持它,比如Ruby:
它可能不是最有效的解决方案,但如果我在这种情况下遇到这样的任务(已知的边界,低边界),它就是我在现实生活中使用的解决方案 . 如果数字的集合非常大,那么我会考虑一种更有效的算法,但在那之前,简单的解决方案对我来说已经足够了 .
尝试找到1到50之间的数字乘积:
设产品,P1 = 1 x 2 x 3 x ............. 50
当您逐个取出数字时,将它们相乘以便得到产品P2 . 但这里缺少两个数字,因此P2 <P1 .
两个mising项的乘积,a x b = P1 - P2 .
你已经知道了总和,b = S1 .
从上述两个方程中,通过二次方程求解a和b . a和b是你缺少的数字 .
我问一个4岁的孩子来解决这个问题 . 他对数字进行了排序,然后计算在内 . 这有一个空间要求O(厨房地板),它工作同样容易,但许多球丢失 .