简单的面试问题变得更难：给出数字1..100，找到丢失的数字-Java 学习之路

1027

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

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 回答

31

尝试找到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是你缺少的数字 .

回复于 2024-04-30T10:29:08+08:00
231
以下是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 .
回复于 2024-04-30T10:29:08+08:00
127

您可以通过阅读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 ，其中还包括伪代码（欢呼！不需要阅读那些棘手的数学公式:)）（谢谢，干得好！） .

回复于 2024-04-30T10:29:08+08:00
537
我们可以通过将数字本身和数字的平方相加来求解Q2 .

然后我们可以将问题减少到
```
k1 + k2 = x
k1^2 + k2^2 = y
```
其中 x 和 y 是总和低于预期值的程度 .

替代给了我们：
```
(x-k2)^2 + k2^2 = y
```
然后我们可以解决以确定我们缺少的数字 .
回复于 2024-04-30T10:29:08+08:00
7
正如@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) 额外的空间 . 然后我们运行以下伪代码算法：
```
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 ） .

第二个循环置换扩展数组，以便如果元素 x 至少出现一次，那么其中一个条目将位于 A[x] 位置 .

请注意，虽然它有一个嵌套循环，但它仍然在 O(N) 时间运行 - 只有 i 这样 A[i] != i 才会发生交换，并且每个交换设置至少一个元素 A[i] == i ，之前不是真的 . 这意味着交换总数（以及 while 循环体的总执行次数）最多为 N-1 .

第三个循环打印那些未被值 i 占用的数组 i 的索引 - 这意味着 i 必定已经丢失 .
回复于 2024-04-30T10:29:08+08:00
4

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

回复于 2024-04-30T10:29:08+08:00
2

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

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

回复于 2024-04-30T10:29:08+08:00
2

我没有检查数学，但我怀疑在计算 Σ(n) 的同一通道中计算 Σ(n^2) 将提供足够的信息以获得两个缺失的数字，如果有三个，则执行 Σ(n^3) ，依此类推 .

回复于 2024-04-30T10:29:08+08:00

基于数字总和的解决方案的问题是它们没有考虑存储和使用具有大指数的数字的成本......在实践中，为了使其适用于非常大的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)) 此算法更直观，具有相同的时间复杂度，并且占用的空间更少 .

回复于 2024-04-30T10:29:08+08:00

-1

等一下 . 正如问题所述，包里有100个号码 . 无论k有多大，问题都可以在恒定时间内解决，因为你可以在一个循环的最多100-k次迭代中使用一个集合并从集合中删除数字 . 100是不变的 . 剩下的数字是你的答案 .

如果我们将解决方案推广到从1到N的数字，除了N不是常数之外什么都没有变化，所以我们处于O（N-k）= O（N）时间 . 例如，如果我们使用位集，我们在O（N）时间内将位设置为1，遍历数字，我们去的时候将位设置为0（O（N-k）= O（N））然后我们得到了答案 .

在我看来，面试官问你如何在O（k）时间而不是O（N）时间打印出最终集的内容 . 显然，通过位设置，您必须遍历所有N位以确定是否应该打印该数字 . 但是，如果更改实现集的方式，则可以以k次迭代打印出数字 . 这是通过将数字放入要存储在哈希集和双向链表中的对象来完成的 . 从哈希集中删除对象时，也会从列表中删除它 . 答案将保留在现在长度为k的列表中 .

回复于 2024-04-30T10:29:08+08:00

这是一个使用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; }
    }
}

回复于 2024-04-30T10:29:08+08:00

14
要解决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个缺失的数字，此算法始终丢弃至少一个分区，因此它保留了快速选择的平均时间复杂度 O(n) . 类似地，如果缺少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);
    }
  }
```
Demo
回复于 2024-04-30T10:29:08+08:00
1

你能检查一下这个号码是否存在吗？如果是，您可以尝试这样做：

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

如果缺少的数字是 x 和 y 那么：

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

所以你检查从 1 到 max(x) 的范围并找到数字

回复于 2024-04-30T10:29:08+08:00
2
可能这个算法可以用于问题1：
- 预先计算前100个整数的xor（val = 1 ^ 2 ^ 3 ^ 4 .... 100）
- xor元素，因为它们不断来自输入流（val1 = val1 ^ next_input）
- 最终答案= 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和a2在 ith 位位置具有不同的奇偶校验 . 现在我们对原始数组进行另一次迭代并保留两个xor值 . 一个用于具有第i位设置的数字，而另一个用于没有第i位设置的数字 . 我们现在有两个数字桶，并保证 a1 and a2 将位于不同的桶中 . 现在重复我们在每个桶上找到一个缺少元素所做的相同操作 .
回复于 2024-04-30T10:29:08+08:00
0
如果您有两个列表的总和和两个列表的乘积，您可以解决Q2 .

（l1是原始的，l2是修改后的列表）
```
d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)
```
我们可以对此进行优化，因为算术系列的总和是第一个和最后一个项的平均值的n倍：
```
n = len(l1)
d = (n/2)*(n+1) - sum(l2)
```
现在我们知道（如果a和b是删除的数字）：
```
a + b = d
a * b = m
```
所以我们可以重新安排到：
```
a = s - b
b * (s - b) = m
```
并且乘出：
```
-b^2 + s*b = m
```
并重新排列，因此右侧为零：
```
-b^2 + s*b - m = 0
```
然后我们可以用二次公式求解：
```
b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b
```
示例Python 3代码：
```
from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5
```
我不知道sqrt，reduce和sum函数的复杂性，所以我无法弄清楚这个解决方案的复杂性（如果有人知道请在下面评论 . ）
回复于 2024-04-30T10:29:08+08:00

166

我认为这可以在没有任何复杂的数学方程和理论的情况下完成 . 以下是现场和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 .

IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

回复于 2024-04-30T10:29:08+08:00

3

对于Q2，这是一个比其他解决方案效率低一点的解决方案，但仍然具有O（N）运行时并且需要O（k）空间 .

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

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

我有一种感觉，这种方法可以推广，并且可能在单次传递输入期间以“并行”方式运行多次搜索，但我还没弄清楚如何 .

回复于 2024-04-30T10:29:08+08:00
1
有一种通用的方法来推广像这样的流式算法 . 我们的想法是使用一些随机化来将'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 .

实际上，通过使用注释中描述的技巧，我们可以比功率和方法更有效 .
回复于 2024-04-30T10:29:08+08:00
0

您可能需要澄清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）空间中适合多少，以及总结所需数量的数量需要多长时间？

回复于 2024-04-30T10:29:08+08:00
32
非常好的问题 . 我会为Qk使用一组差异 . 许多编程语言甚至都支持它，比如Ruby：
```
missing = (1..100).to_a - bag
```
它可能不是最有效的解决方案，但如果我在这种情况下遇到这样的任务（已知的边界，低边界），它就是我在现实生活中使用的解决方案 . 如果数字的集合非常大，那么我会考虑一种更有效的算法，但在那之前，简单的解决方案对我来说已经足够了 .
回复于 2024-04-30T10:29:08+08:00
4

我会采用不同的方法解决这个问题，然后向访调员探讨他正试图解决的更大问题的更多细节 . 根据问题及其周围的要求，明显的基于集合的解决方案可能是正确的，并且生成列表和后续选择方法可能不是 .

例如，可能是面试官要发送 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 的任何值（即使它未提前知道），并且在上面的示例中，它以最小化最关键区间的方式应用 .

回复于 2024-04-30T10:29:08+08:00
0

您可以通过在对称性（组，数学语言）方面考虑它来激发解决方案 . 无论数字集的顺序如何，答案应该是相同的 . 如果您要使用 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 .

回复于 2024-04-30T10:29:08+08:00
6
另一种方法是使用残差图过滤 .

假设我们有数字1到4而缺少3 . 二进制表示如下，

1 = 001b，2 = 010b，3 = 011b，4 = 100b

我可以创建如下的流程图 .
```
1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1
```
请注意，流程图包含x个节点，而x是位数 . 并且最大边数是（2 * x）-2 .

因此对于32位整数，它将占用O（32）空间或O（1）空间 .

现在如果我从1,2,4开始删除每个数字的容量，那么我剩下一个残差图 .
```
0 ----------> 1 ---------> 1
```
最后我将运行如下的循环，
```
result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)
```
现在结果是 result 包含不丢失的数字（误报） . 但 k <= (size of the result) <= n 时有 k 缺少元素 .

我将最后一次通过给定的列表来标记结果是否丢失 .

所以时间复杂度将是O（n） .

最后，通过获取节点 00 ， 01 ， 11 ， 10 而不仅仅是 0 和 1 ，可以减少误报的数量（以及所需的空间） .
回复于 2024-04-30T10:29:08+08:00
1

您可以尝试使用Bloom Filter . 将包中的每个数字插入到bloom中，然后遍历完整的1-k集，直到报告每个未找到的数字 . 这可能无法在所有情况下找到答案，但可能是一个足够好的解决方案 .

回复于 2024-04-30T10:29:08+08:00
1
我相信我有一个 O(k) 时间和 O(log(k)) 空间算法，假设您有 floor(x) 和 log2(x) 函数可用于任意大整数：

你有一个 k -bit长整数（因此是 log8(k) 空格），你可以在其中添加 x^2 ，其中x是你在包中找到的下一个数字： s=1^2+2^2+... 这需要 O(N) 时间（对于访调员来说这不是问题） . 最后你会得到 j=floor(log2(s)) 这是你正在寻找的最大数字 . 然后 s=s-j 然后你再做一次上面的事情：
```
for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}
```
现在，您通常没有 2756 -bit整数的floor和log2函数，而是双精度函数 . 所以？简单地说，对于每2个字节（或1或3，或4）您可以使用这些函数来获得所需的数字，但这会增加时间复杂度. O(N) 因子
回复于 2024-04-30T10:29:08+08:00
117

这可能听起来很愚蠢，但是，在提交给您的第一个问题中，您必须看到包中的所有剩余数字才能实际添加它们以使用该等式找到丢失的数字 .

所以，既然你可以看到所有数字，只需查找缺少的数字 . 当缺少两个数字时也是如此 . 我觉得很简单 . 当你看到袋子里剩下的数字时，没有必要使用方程式 .

回复于 2024-04-30T10:29:08+08:00
0
我认为这可以概括为：

将S，M表示为算术系列和乘法之和的初始值 .
```
S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n
```
我应该考虑一个计算这个的公式，但这不是重点 . 无论如何，如果缺少一个数字，您已经提供了解决方案 . 但是，如果缺少两个数字，那么我们用S1和M1表示新的总数和总数，如下所示：
```
S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)
```
由于你知道S1，M1，M和S，上面的等式可以解决找到a和b，缺失的数字 .

现在缺少三个数字：
```
S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)
```
现在你的未知数是3，而你只有两个可以解决的方程式 .
回复于 2024-04-30T10:29:08+08:00
0
我不知道这是否有效，但我想建议这个解决方案 .
- 计算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，如果是，我们就完成了 .

如果我错了，请纠正我，如果这是正确的，还要评论时间复杂性
回复于 2024-04-30T10:29:08+08:00
-1
我们大部分时间都可以在 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 .
回复于 2024-04-30T10:29:08+08:00

可能的解决方案：

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

回复于 2024-04-30T10:29:08+08:00

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

澄清

30 回答

相关问题