3

摘自《Programming Pearls 2nd Edition》一书，引用第 2 列第 2.1 节中的问题 A

给定一个包含最多 40 亿个随机整数的顺序文件，找到一个不在文件中的 32 位整数（并且必须至少缺少一个 - 为什么？）。你将如何用大量的主存来解决这个问题？如果您可以使用几个外部“临时”文件但只有几百字节的主存储器，您将如何解决它？

问题陈述说“最多”四十亿个整数。因此，一个有效输入可能在 100 - 299 范围内，但缺少一个数字。如果对问题陈述的这种理解是正确的，那么这个问题所需的输入是包含数字的文件以及文件中数字的范围，即：i 到 n。

对于这个问题，以下 O(n) 解决方案不是比书中给出的解决方案（来自 Ed Reingold）更直观吗？还是我错过了什么？

假设给定的范围是 i...n

using the forumla (n * (n + 1) / 2) 
  x = the sum of numbers from 1 to i-1 
  y = the sum of numbers from 1 to n 
walk through the input and get a sum of the numbers (value z)

missing number = (y - x - z)
4

1 回答 1

4

你错过了一些东西：

  1. 这些数字并不是唯一的，求和方法假定唯一的元素并且在该范围内只有一个缺失
  2. 您不知道数字的范围，在 32 位整数中可以有比 4B 多得多的元素（准确地说，还有 294967296 个数字可以用 32 位表示，然后是 4B）

看一下简化的反例range = [1,5], array = [5,5,5,4,1]。
在这种情况下，您将获得x=1, y = 15, z = 20.
但是，20-15-1 = 4，它并没有丢失。

您可以使用在这种情况下运行的radix sortO(n)（因为 32 位是恒定的），然后扫描已排序的数组以查找第一个丢失的元素。

编辑：一种更有效的方法是使用基数排序和选择算法的变体：

  1. 让您当前的位数为k. 查看第一位，并将数组分成两部分，第一部分未设置该位，第二部分设置该位。
  2. 在至少其中一个部分中 - 必须少于(2^k) / 2 = 2^(k-1)元素。
  3. 仅将问题减少到此子数组并使用k' = k-1 （减少当前位数）并返回 1。

继续这样做，直到你用尽你的比特，你会得到一个不在原始列表中的数字。

请注意，假设列表足够随机，算法的复杂性是O(n)- 对于任意数量的位（而不是O(n*k)）

于 2012-12-28T10:00:52.833 回答