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

Question

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

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:如果行李中缺少k个号码,您会如何有效地找到它？

这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.

所以这里的问题很简单:

• 你会如何解决Q2？
• 你会如何解决Q3？
• 你怎么解决Qk？

---

澄清

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

所以,当然你必须扫描输入O(N),但你只能捕获少量的信息(用k而不是N来定义),然后必须以某种方式找到k个缺失的数字.

Answer 1

以下是Dimitris Andreou 链接的摘要.

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

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

使用牛顿的身份,知道b _i允许计算

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

如果扩展多项式(xa ₁)...(xa _k),系数将精确地为c ₁,...,c _k - 请参阅Viète的公式.由于每个多项式因子唯一(多项式环是欧几里德域),这意味着_i是唯一确定的,直到排列.

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

然而,当k变化时,计算c ₁,...,c _k的直接方法是非常昂贵的,因为例如c _k是所有缺失数的乘积,幅度为n!/(nk)!.为了克服这一点,在Z _q字段中执行计算,其中q是素数,使得n <= q <2n - 它由Bertrand的假设存在.证明不需要改变,因为公式仍然成立,并且多项式的因子分解仍然是唯一的.您还需要一种用于有限域分解的算法,例如Berlekamp或Cantor-Zassenhaus的算法.

常数k的高级伪代码:

• 计算给定数字的第i个幂
• 减去得到未知数的第i个幂的总和.拨打总和b _i.
• 使用牛顿的恒等式来计算b _i的系数; 叫他们_我.基本上,c ₁ = b ₁ ; c ₂ =(c ₁ b ₁ -b ₂)/ 2; 请参阅维基百科的确切公式
• 因子多项式x ^k -c ₁ x ^k-1 + ... + c _k.
• 多项式的根是所需的数字a ₁,...,a _k.

对于变化的k,使用例如Miller-Rabin找到素数n <= q <2n,并执行所有以q为模的数量减少的步骤.

编辑:该答案的先前版本表明,代替Z _q,其中q是素数,可以使用特征2的有限域(q = 2 ^(log n)).情况并非如此,因为牛顿的公式需要按数字除以k.

Answer 2

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

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

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

Answer 3

我们可以通过将数字本身和数字的平方相加来求解Q2 .

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

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

凡x和y是资金多远低于预期值.

替代给了我们:

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

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

Answer 4

正如@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必须丢失.

Answer 5

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

Answer 6

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

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

Answer 7

我没有检查过数学,但是我怀疑?(n^2)在我们计算的相同通道中进行计算?(n)会提供足够的信息来获得两个缺失的数字,?(n^3)如果有三个则执行,依此类推.

Answer 8

基于数字总和的解决方案的问题是它们没有考虑存储和处理具有大指数的数字的成本......在实践中,为了使其适用于非常大的n,将使用大数字库.我们可以分析这些算法的空间利用率.

我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度.

存储:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

所以 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)时间,总时间:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

使用的总时间: \Theta(kn log n)

如果这个时间和空间令人满意,您可以使用简单的递归算法.设b!i是包中的第i个条目,n是删除前的数字,k是删除的数量.在Haskell语法中......

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

使用的存储:O(k)用于列表,O(log(n))用于堆栈:O(k + log(n)) 此算法更直观,具有相同的时间复杂度,并且占用更少的空间.

Answer 9

等一下.正如问题所述,包里有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的列表中.

Answer 10

Q2 的一个非常简单的解决方案，我很惊讶没有人已经回答了。使用 Q1 中的方法找到两个缺失数字的总和。让我们用 S 表示它，然后缺失的数字之一小于 S/2，另一个大于 S/2（废话）。对从 1 到 S/2 的所有数字求和，并将其与公式的结果（类似于 Q1 中的方法）进行比较，以找到缺失数字之间的较低者。从 S 中减去它以找到更大的缺失数。

Answer 11

要解决2(和3)缺失数字问题,您可以修改quickselect,平均运行O(n)并使用常量内存,如果分区就地完成.

1. 将集合相对于随机枢轴p划分为分区l,分区包含小于枢轴的r数字,并且包含大于枢轴的数字.

2. 通过将数据透视值与每个分区的大小进行比较来确定2个缺失数字所在的分区(p - 1 - count(l) = count of missing numbers in l和 n - count(r) - p = count of missing numbers in r)

3. 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个缺失的数字,该算法总是丢弃至少一个分区,因此它保留O(n)了quickselect的平均时间复杂度.类似地,如果缺少3个数字,则该算法还会在每次传递时丢弃至少一个分区(因为与2个缺失的数字一样,最多只有1个分区将包含多个缺失的数字).但是,当添加更多缺失数字时,我不确定性能会下降多少.

这是一个不使用就地分区的实现,所以这个例子不满足空间要求,但它确实说明了算法的步骤:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

演示

Answer 12

\n

动机

\n

如果你想解决一般情况的问题，并且可以存储和编辑数组，那么Caf 的解决方案是迄今为止最有效的。如果无法存储数组（流版本），那么sdcvvc 的答案是当前建议的唯一解决方案类型。

\n

如果您可以存储数组但无法编辑它，我提出的解决方案是最有效的答案（到目前为止在这个线程上），我从Svalorzen 的解决方案中得到了这个想法，它解决了 1 或 2 个丢失的项目。这个解决方案需要\xce\x98(k*n)时间O(min(k,log(n)))并且\xce\xa9(log(k))。它也适用于并行性。

\n

概念

\n

这个想法是，如果您使用比较总和的原始方法：
\nsum = SumOf(1,n) - SumOf(array)

\n

...然后取缺失数字的平均值：
\naverage = sum/n_missing_numbers

\n

...它提供了一个边界：在缺失的数字中，保证至少有一个数字小于或等于average，并且 至少有一个数字大于average。这意味着我们可以分成子问题，每个子问题扫描数组[O(n) ] 并且只关心它们各自的子数组。

\n

代码

\n

C 风格的解决方案（不要因为全局变量而评判我，我只是想让代码对非 C 语言的人可读）：

\n

#include "stdio.h"\n\n// Example problem:\nconst int array [] = {0, 7, 3, 1, 5};\nconst int N = 8; // size of original array\nconst int array_size = 5;\n\nint SumOneTo (int n)\n{\n    return n*(n-1)/2; // non-inclusive\n}\n\nint MissingItems (const int begin, const int end, int & average)\n{\n    // We consider only sub-array elements with values, v:\n    // begin <= v < end\n    \n    // Initialise info about missing elements.\n    // First assume all are missing:\n    int n = end - begin;\n    int sum = SumOneTo(end) - SumOneTo(begin);\n\n    // Minus everything that we see (ie not missing):\n    for (int i = 0; i < array_size; ++i)\n    {\n        if ((begin <= array[i]) && (array[i] < end))\n        {\n            --n;\n            sum -= array[i];\n        }\n    }\n    \n    // used by caller:\n    average = sum/n;\n    return n;\n}\n\nvoid Find (const int begin, const int end)\n{\n    int average;\n\n    if (MissingItems(begin, end, average) == 1)\n    {\n        printf(" %d", average); // average(n) is same as n\n        return;\n    }\n    \n    Find(begin, average + 1); // at least one missing here\n    Find(average + 1, end); // at least one here also\n}\n\nint main ()\n{   \n    printf("Missing items:");\n    \n    Find(0, N);\n    \n    printf("\\n");\n}\n

\n

分析

\n

暂时忽略递归，每个函数调用显然都需要O(n)时间和O(1)空间。请注意，sum可以等于n(n-1)/2，因此需要存储所需位数的两倍n-1。至多这意味着我们实际上需要两个额外元素的空间，无论数组 或 的大小如何，因此在正常约定下k它仍然是空间。O(1)

\n

对于缺失的元素有多少函数调用并不那么明显k，所以我将提供一个视觉效果。您的原始子数组（连接数组）是完整数组，其中包含所有k缺失的元素。我们将按递增顺序想象它们，其中--表示连接（同一子数组的一部分）：

\n

m ₁ -- m ₂ -- m ₃ -- m ₄ -- (...) -- m _k-1 -- m _k

\n

该函数的作用Find是将缺失的元素断开到不同的不重叠的子数组中。它保证每个子数组中至少有一个缺失元素，这意味着恰好中断一个连接。

\n

这意味着，无论分割如何发生，它总是需要k-1 Find函数调用来完成查找仅缺少一个元素的子数组的工作。

\n

所以时间复杂度是\xce\x98((k-1 + k) * n) = \xce\x98(k*n)。

\n

对于空间复杂度，如果我们每次按比例相除，就会得到O(log(k))空间复杂度，但如果我们一次只分离一个，就会得到O(k)。

\n

请参阅此处，了解为什么空间复杂度为 的证明O(log(n))。鉴于上面我们已经证明它也是O(k)，那么我们就知道它是O(min(k,log(n)))。

\n

Answer 13

这是一个使用k位额外存储的解决方案,没有任何巧妙的技巧,只是简单明了.执行时间O(n),额外空间O(k).只是为了证明这可以在不首先阅读解决方案或成为天才的情况下解决:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Answer 14

对于 Q2，这是一个比其他解决方案效率更低的解决方案，但仍然具有 O(N) 运行时间并占用 O(k) 空间。

这个想法是将原始算法运行两次。在第一个中，您会得到一个缺失的总数，它为您提供了缺失数字的上限。我们打这个号码吧N。您知道缺少的两个数字的总和为N，因此第一个数字只能在间隔中，[1, floor((N-1)/2)]而第二个数字将在 中[floor(N/2)+1,N-1]。

因此，您再次循环所有数字，丢弃未包含在第一个间隔中的所有数字。那些是，你跟踪他们的总和。最后，您将知道缺少的两个数字之一，并通过扩展知道第二个。

我有一种感觉，这种方法可以推广，并且可能在一次通过输入时以“并行”方式运行多个搜索，但我还没有弄清楚如何进行。

Answer 15

你能检查每个数字是否存在吗？如果是，您可以尝试以下方法：

S =袋子中所有数字的总和（S <5050）
Z =缺少数字5050-S的总和

如果丢失的号码是x和y，则：

x = Z-y和
max（x）= Z-1

因此，您检查从1到的范围max(x)并找到数字

Answer 16

可能这个算法适用于问题 1：

1. 预计算前 100 个整数的异或（val=1^2^3^4....100）
2. 对来自输入流的元素进行异或（val1=val1^next_input）
3. 最终答案=val^val1

或者甚至更好：

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

该算法实际上可以针对两个缺失的数字进行扩展。第一步保持不变。当我们用两个缺失的数字调用 GetValue 时，结果将是a1^a2两个缺失的数字。可以说

val = a1^a2

现在为了从 val 中筛选出 a1 和 a2，我们在 val 中取任何设置位。假设该ith位在 val 中设置。这意味着 a1 和 a2ith在位位置具有不同的奇偶校验。现在我们对原始数组进行另一次迭代并保留两个 xor 值。一个用于设置第 i 位的数字和其他没有设置第 i 位的数字。我们现在有两个数字桶，它的保证a1 and a2将位于不同的桶中。现在重复我们为在每个桶上查找一个缺失元素所做的相同操作。

Answer 17

有一种通用方法可以解决此类流媒体问题。这个想法是使用一点随机化来希望将k元素“分散”到独立的子问题中，我们的原始算法可以为我们解决问题。该技术用于稀疏信号重建等。

• a创建一个大小为 的数组u = k^2。
• 选择任何通用哈希函数, h : {1,...,n} -> {1,...,u}。（如乘法移位）
• 对于每一个i增加1, ..., na[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情况下的时间。

事实上，通过使用评论中描述的技巧，我们甚至可以比幂和方法更有效。