algorithm - 寻找丢失的号码？

Question

我遇到了这个非常有趣的问题？我有 3 亿个 SSN 号码（9 位号码）

找到丢失的 SSN 号码？

您有无限的驱动器空间，但只有 2MB 的 RAM？

Answer 1

假设只有一个元素丢失.. 由于我们有内存限制，我们需要将文件部分加载到内存中，因此划分给定文件 3*10pow(8)/2MB 并将以下方法应用于部分文件（从外部排序借用的技术）。该技术很简单 XOR 所有元素。基本概念来自汉明码。如果我们对从 1 到 2power(n-1) 的所有元素进行异或运算，结果应该等于零。如果缺少元素，则结果将是缺少数字。

在忙碌的方法中：我们还可以应用从 1 到 n 的自然数的算术和，即 n(n+1)/2，然后在一次遍历中计算给定数组的总和并找到 n(n+1)/2 之间的差并获得总和。它应该给出缺失的数字。由于十亿数字的总和是一个非常大的数字。

Answer 2

让我们首先分析一个较小的问题。假设您有 9 个唯一的 1 位数字，并且您正试图找到丢失的那个。您可以做的是将 10 个唯一的 1 位数字相加：

0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

然后，您可以将您拥有的 9 个数字相加并减去差值以找到缺少的数字。可以将相同的策略应用于您的问题，但问题在于找到总和，因为如果可能的话，您不想手动进行。

让我们看一下 100 个唯一的 2 位数字的情况：

前 10 个数字 = 45（如上图）

接下来的 10 个数字都将有一个额外的 10 + 1 位数字值，给我们一个 145 的结果。接下来的 10 个，每个都有一个额外的 20 -> 245，依此类推，直到我们得到最后 10 个具有总和的数字945。我们将这些加在一起得到 4950。

现在，让我们寻找与数字数量相关的模式。

1 位 = 45（那里没有太多内容，但它确实提供了一个额外的数据点来验证）

2 位数 = 4950

让我们回想一下我们是如何添加数字的，首先看 2 位数的情况可能更容易。

让我们将 x 称为 1 到 9 中最左边的数字。我们会将先前位数的答案添加到 10 *（x -> 之后有 1 个零，如果是 2 位数的解决方案。）所以在这里我们可以再次利用我们找到的 1 位数的答案并看到10 * 10 + 20 * 10 + 30 * 10 + 40 * 10 + 50 * 10 + 60 * 10 + 70 * 10 + 80 * 10 + 90 * 10 = 10 * (10 + 20 + 30 + 40 + 50 + 60 + 70 + 80 + 90) = 100 * (1+2+3+4+5+6+7+8+9) = 100 * 45 = 4500。然后我们也有 45 十次，所以得到我们 450。4500 + 450 = 4950。

现在，是时候推广到递归方程了。

所有 n 位唯一数字的总和 =

1（后面有 n 个零）* ans(n-1) + 1（有 n-1 个零）* ans(n-1) + 1（有 n-2 个零）* ans(n-2) ... 10 * 45 + 1 * 0

我已经完成了进一步的分解，但我希望我说清楚了，这也能用一些数学乐趣回答你的问题！