题 简单的面试问题变得更难:给出数字1..100,找到丢失的数字


我有一段时间有一个有趣的面试经历。问题开始很简单:

Q1:我们有一个包含数字的包 123,..., 100。每个数字只出现一次,因此有100个数字。现在从包里随机挑出一个号码。找到丢失的号码。

当然,我之前听过这个采访问题,所以我很快回答了以下问题:

A1:嗯,数字的总和 1 + 2 + 3 + … + N 是 (N+1)(N/2) (看到 维基百科:算术系列的总和)。对于 N = 100,总和是 5050

因此,如果包中存在所有数字,则总和将是精确的 5050。由于缺少一个数字,总和将小于此数值,差异就是该数字。所以我们可以找到丢失的号码 O(N) 时间和 O(1) 空间。

在这一点上,我认为我做得很好,但突然之间问题发生了意想不到的转变:

Q2:这是正确的,但现在你如何做到这一点  号码丢失了?

我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题。面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一次传递中收集了一些信息后再进行第二次传递,但我真的只是在拍摄在黑暗中而不是实际上有一条清晰的解决方案。

面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法。在这一点上,我有点不高兴(因为事先不知道答案),并询问这是否是一般(读取:“有用”)编程技术,或者它只是一个技巧/问题答案。

面试官的回答让我感到惊讶:你可以推广这项技术,找到3个缺失的数字。事实上,你可以概括它来找到 ķ 缺少数字。

QK:如果确切的话 ķ 袋子上缺少数字,你怎么能有效地找到它?

这是几个月前,我仍然无法弄清楚这种技术是什么。显然有一个 Ω(N) 时间下限因为我们必须至少扫描一次所有数字,但面试官坚持认为 时间 和 空间 解决技术的复杂性(减去 O(N) 时间输入扫描)定义于 ķ 不 ñ

所以这里的问题很简单:

  • 你会如何解决? Q2
  • 你会如何解决? Q3
  • 你会如何解决? QK

澄清

  • 一般来说都有 ñ 数字来自1 ..ñ,而不仅仅是1..100。
  • 我不是在寻找明显的基于集合的解决方案,例如用一个 位设置,编码每个数字的存在/不存在由指定位的值编码,因此使用 O(N)额外空间中的位。我们无法承受任何与之成比例的额外空间 ñ
  • 我也不是在寻找明显的排序优先方法。这一点和基于集合的方法在一次采访中值得一提(它们很容易实现,并且取决于 ñ,可以很实用)。我正在寻找圣杯解决方案(可能实现也可能不实用,但仍具有所需的渐近特征)。

所以,当然你必须扫描输入 O(N),但您只能捕获少量信息(根据 ķ 不 ñ),然后必须找到 ķ 某种程度上缺少数字。


986
2017-08-16 10:26


起源


@polygenelubricants感谢您的澄清。 “我正在寻找一种使用O(N)时间和O(K)空间的算法,其中K是缺席数字的数量”从一开始就已经清楚了;-) - Dave O.
您应该在Q1的声明中准确地说明您无法按顺序访问这些数字。这对你来说似乎很明显,但我从来没有听说过这个问题而且“bag”这个术语(也就是“multiset”)有点令人困惑。 - Jérémie
请阅读以下内容,因为这里提供的答案很荒谬: stackoverflow.com/questions/4406110/...
除非您将无界整数的空间要求视为O(1),否则求和数的解决方案需要log(N)空间。但是如果你允许无界的整数,那么你只需要一个整数就可以拥有所需的空间。 - Udo Klein
这是一个人为的问题。包本身已经消耗了O(N)空间,使用位阵列来跟踪包中的元素不会使这更糟。 - toongeorges


答案:


以下是摘要 Dimitris Andreou的 链接。

记住i次幂的总和,其中i = 1,2,...,k。这减少了求解方程组的问题

一个1 + a2 + ... + aķ = b1

一个12 + a22 + ... + aķ2 = b2

...

一个1ķ + a2ķ + ... + aķķ = bķ

运用 牛顿的身份知道b一世 允许计算

C1 = a1 + a2 + ... aķ

C2 = a1一个2 + a1一个3 + ... + ak-1的一个ķ

...

Cķ = a1一个2 ... 一个ķ

如果展开多项式(x-a1)...(X-Aķ)系数将完全是c1, ..., Cķ  - 看 Viète的公式。因为每个多项式因子都是唯一的(多项式环是一个 欧几里德域),这意味着一个一世 是唯一确定的,直到排列。

这结束了一个证据,即记住功率足以恢复数字。对于常数k,这是一个很好的方法。

但是,当k变化时,计算c的直接方法1,...,Cķ 是非常昂贵的,因为例如Cķ 是所有缺失数字的乘积,幅度为n!/(n-k)!为了克服这个问题,在Z中执行计算q 字段,其中q是素数,使得n <= q <2n - 它存在于 伯特兰的假设。证明不需要改变,因为公式仍然成立,并且多项式的因子分解仍然是唯一的。您还需要一种算法来对有限域进行因子分解,例如一个算法 伯利坎普 要么 康托尔 - Zassenhaus

常数k的高级伪代码:

  • 计算给定数字的第i个幂
  • 减去得到未知数的第i个幂的总和。拨打总和b一世
  • 使用牛顿的恒等式来计算b的系数一世;叫他们c一世。基本上,c1 = b1; C2 =(c1b1  - b2)/ 2;请参阅维基百科的确切公式
  • 对多项式x进行分解ķ-C1Xk-1的 + ... + cķ
  • 多项式的根是所需的数字a1, ..., 一个ķ

对于变化的k,使用例如,找到素数n <= q <2n。米勒 - 拉宾,并执行所有数字减少模数q的步骤。

正如Heinrich Apfelmus评论的那样,你可以使用q = 2而不是素数q⌈logn⌉ 并执行 有限域算法


514
2017-08-16 12:13



您不必使用素数字段,也可以使用 q = 2^(log n)。 (你是如何制作超级和下标的?!) - Heinrich Apfelmus
此外,由于公式$ c ^ {k + 1} _m = c ^ k_ {m + 1} + c ^ k_m x_ {k + 1} $,您可以动态计算c_k,而无需使用功率和。其中上标$ k $表示变量数,$ m $表示对称多项式的次数。 - Heinrich Apfelmus
+1这真的非常聪明。与此同时,这是值得怀疑的,是否真的值得努力,或者这个解决方案是否可以以另一种方式重复使用。即使这是一个现实世界的问题,在许多平台上也是最微不足道的 O(N^2) 解决方案可能会超出这个美丽甚至相当高 N。让我想起这个: tinyurl.com/c8fwgw 尽管如此,干得好!我不会耐心地爬过所有的数学:) - back2dos
我认为这是一个很好的答案。我认为这也说明了如何将缺失的数字扩展到一个以上的面试问题。即使是第一种也是一种苦行僧,但它很常见,它基本上表明“你做了一些面试准备”。但是期望CS专业知道超过k = 1(特别是在采访中“当场”)有点傻。 - corsiKa
我打赌输入所有号码 hash set 并迭代 1...N 套件使用查找来确定数字是否丢失,将是最通用的,平均最快的 k 变体,最可调试的最易维护和可理解的解决方案。当然,数学方式令人印象深刻,但在某些方面你需要成为一名工程师,而不是数学家。特别是涉及业务时。 - v.oddou


你会通过阅读几页来找到它 Muthukrishnan - 数据流算法:谜题1:找到丢失的数字它显示了您正在寻找的概括。这可能是你的面试官阅读的内容以及他提出这些问题的原因。

现在,如果只有人们会开始删除被Muthukrishnan治疗所包含或取代的答案,并使这个文本更容易找到。 :)


另见 sdcvvc的 直接相关的答案,其中还包括伪代码(欢呼!不需要阅读那些棘手的数学公式:))(谢谢,干得好!)。


226
2017-08-16 11:26



你怎么翻译 那进入代码?!? - Eldelshell
噢...这很有趣。我不得不承认我对数学有点困惑,但我正在略读它。可能会保持开放以便稍后查看。 :)和+1让这个链接更容易找到。 ;-) - Chris
谷歌图书链接对我不起作用。这里一个 更好的版本 [PostScript文件]。 - Heinrich Apfelmus
哇。我没想到这会被投票!上次我发布了对解决方案的引用(Knuth's,在这种情况下)而不是试图自己解决它,它实际上是downvoted: stackoverflow.com/questions/3060104/... 我内心的图书管理员很高兴,谢谢:) - Dimitris Andreou
请阅读以下内容,因为这里提供的答案很荒谬: stackoverflow.com/questions/4406110/...


我们可以通过将数字本身和数字相加来解决Q2 广场 数字。

然后我们可以将问题减少到

k1 + k2 = x
k1^2 + k2^2 = y

哪里 x 和 y 是总和低于预期值的程度。

替代给了我们:

(x-k2)^2 + k2^2 = y

然后我们可以解决以确定我们缺少的数字。


159
2017-08-16 10:37



+1;我已经在Maple中尝试了选择数字的公式并且它有效。不过,我仍然无法说服自己为什么这样做。 - polygenelubricants
@polygenelubricants:如果你想证明正确性,你首先会证明它总是提供 一个 正确的解决方案(也就是说,它总是产生一对数字,当从集合中移除它们时,将导致集合的其余部分具有观察到的和和平方和)。从那里,证明唯一性就像显示它只产生一对这样的数字一样简单。 - Anon.
方程的性质意味着你将从该方程得到两个k2值。但是,从用于生成k1的第一个方程式中,您可以看到k2的这两个值将意味着k1是另一个值,因此您有两个相同数字的解决方案。如果你讽刺地声明k1> k2那么你只能得到二次方程的一个解,因此整体上有一个解。显然,问题的本质是答案总是存在,所以它始终有效。 - Chris
对于给定的和k1 + k2,有许多对。我们可以将这些对写为K1 = a + b和K2 = a-b,其中a =(K1 + k2 / 2)。 a对于给定的总和是唯一的。平方和(a + b)** 2 +(a-b)** 2 = 2 *(a2 + b2)。对于给定的和K1 + K2,a2项是固定的,我们看到由于b,正方形的总和将是唯一的2学期。因此,值x和y对于一对整数是唯一的。 - phkahler
这太棒了。 @ user3281743这是一个例子。让缺失的数字(k1和k2)为4和6.总和(1 - > 10)= 55和总和(1 ^ 2 - > 10 ^ 2)= 385.现在让x = 55 - (总和(所有剩余数字) ))和y = 385 - (总和(所有剩余数字的平方))因此x = 10和y = 52.如图所示替换为我们留下:(10 - k2)^ 2 + k2 ^ 2 = 52你可以简化为:2k ^ 2 - 20k + 48 = 0.求解二次方程式给出4和6作为答案。 - AlexKoren


正如@j_random_hacker指出的那样,这非常相似 在O(n)时间和O(1)空间中查找重复项,我的答案也适用于此。

假设“bag”由基于1的数组表示 A[] 大小 N - k,我们可以解决Qk O(N) 时间和 O(k) 额外的空间。

首先,我们扩展我们的数组 A[] 通过 k 元素,现在它的大小 N。这是 O(k) 额外的空间。然后我们运行以下伪代码算法:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化 k 额外的条目与数组中的第一个条目相同(这只是我们知道已经存在于数组中的一个方便的值 - 在此步骤之后,在初始数组中缺少任何条目 N-k 在扩展数组中仍然缺失)。

第二个循环置换扩展数组,以便if元素 x 至少出现一次,然后其中一个条目就位 A[x]

请注意,虽然它有一个嵌套循环,但仍然可以运行 O(N) 时间 - 只有在有时才会发生交换 i 这样的 A[i] != i,并且每个交换设置至少一个元素 A[i] == i,之前的情况并非如此。这意味着交换的总数(以及因此的总执行次数) while 循环体)最多 N-1

第三个循环打印数组的索引 i 没有被价值占据的 i - 这意味着 i 肯定是失踪了。


120
2018-04-22 04:32



我想知道为什么这么少的人投票给这个答案,甚至没有把它标记为正确的答案。这是Python中的代码。它在O(n)时间内运行,需要额外的空间O(k)。 pastebin.com/9jZqnTzV - wall-e
@caf这非常类似于设置位和计数位为0的位置。我认为在创建整数数组时会占用更多内存。 - Fox
“设置位并计算位为0的位置”需要O(n)额外空间,此解决方案显示如何使用O(k)额外空间。 - caf
不能使用流作为输入并修改输入数组(虽然我非常喜欢它并且这个想法很有成效)。 - comco
@ v.oddou:不,没关系。交换将改变 A[i],这意味着下一次迭代不会比较前两次的相同的两个值。新的 A[i] 将与最后一个循环相同 A[A[i]],但新的 A[A[i]] 将是一个 新 值。试试看吧。 - caf


我问一个4岁的孩子来解决这个问题。他对数字进行了排序,然后计算在内。这有一个空间要求O(厨房地板),它工作同样容易,但许多球丢失。


115
2018-04-12 18:59



;)你的4岁儿童必须接近5或/并且是天才。我4岁的女儿甚至不能算到4岁。公平地说,她说她刚刚完全融入了“4”的存在。否则直到现在她总是会跳过它。 “1,2,3,5,6,7”是她通常的计数序列。我让她把铅笔加在一起,她会通过从头开始重新编号来管理1 + 2 = 3。我真的很担心...:'(meh .. - v.oddou
简单而有效的方法。 - PabTorre
O(厨房地板)哈哈 - 但不是O(n ^ 2)?
O(m²)我猜:) - Viktor Mellgren


不确定,如果它是最有效的解决方案,但我会遍历所有条目,并使用bitset记住,设置哪些数字,然后测试0位。

我喜欢简单的解决方案 - 我甚至相信,它可能比计算总和或平方和等更快。


30
2017-08-16 10:38



我确实提出了这个明显的答案,但这不是面试官想要的。我在问题中明确表示,这不是我正在寻找的答案。另一个明显的答案:排序第一。不是 O(N) 数排序也不算 O(N log N) 比较排序是我正在寻找的,虽然它们都是非常简单的解决方案。 - polygenelubricants
@polygenelubricants:我在你的问题中找不到你说的那个地方。如果你认为bitset是结果,那么就没有第二遍。复杂性是(如果我们认为N是不变的,正如采访者所说的那样,复杂性是“定义的” ķ 不是N“)O(1),如果你需要构造一个更”干净“的结果,你得到O(k),这是你能得到的最好的,因为你总是需要O(k)来创建干净的结果。 - Chris Lercher
“请注意,我不是在寻找明显的基于集合的解决方案(例如,使用位集,”。原始问题的第二段。 - hrnt
@hmt:是的,问题是几分钟前编辑的。我只是给出答案,我希望来自受访者......人为地构建一个次优解决方案(无论你做什么都不能超过O(n)+ O(k)时间)对我有意义 - 除非你无法承担额外的O(n)空间,但问题并不明确。 - Chris Lercher
我再次编辑了这个问题以进一步澄清。我很感激反馈/回答。 - polygenelubricants


我没有检查数学,但我怀疑是计算 Σ(n^2) 在我们计算的同一通道中 Σ(n) 将提供足够的信息来获得两个缺失的数字,Do Σ(n^3) 如果有三个,依此类推。


29
2017-08-16 10:38