3

问题：输入在顺序文件上。该文件最多包含 40 亿个整数。找到一个缺失的整数。

根据我的理解解决方案：

  1. 制作两个临时文件，一个以 0 开头，另一个以 1 开头

  2. 两个必须（4.3B 鸽洞和 4B 鸽子）中的一个小于 2B。选择文件并在第 2 位重复步骤 1 和 2，然后在第 3 位重复步骤，依此类推..

这个迭代的结束条件是什么？

此外，这本书提到算法的效率是 O(n) 但是，

第一次迭代 => n 次探测操作
第二次迭代 => n/2 次探测操作
。
.
.
n + n/2 + n/4 +... 1 => nlogn??

我错过了什么吗？

4

2 回答 2

4

您将检查这两个文件并选择具有最少元素的文件。

您将重复该过程，直到您完成所有 32 位，最后您将拥有一个文件 0 元素。这应该是丢失的数字之一。因此，如果您一直在跟踪到目前为止已过滤的位，您就会知道该数字应该是多少。

请注意，这是为了找到一个（即“任何”）缺失的数字。如果给定一个包含 40 亿个（不是2^32(4294967296)）个整数的（无序的）顺序列表，其中一个缺失，您必须找到，这将不起作用，因为您可以从一开始就切断缺失的整数。

还：

n + n/2 + n/4 + ... 1 <= 2n

不是n log n。

它是一个几何序列，a = n, r = 1/2可以用公式计算：

n (1-(1/2)^m)
-------------
  1 - (1/2)

因为0 < (1/2)^m < 1对于任何正数m（因为0 < 1/2 < 1），我们可以说(1-r^m) < 1，因此我们可以说最大值是：

  n.1
-------
1 - 1/2

   n
= ---
  1/2

= 2n
于 2013-10-16T08:31:25.827 回答
2

如果只有 1 个缺失值，则意味着您具有以下条件：

  1. 文件包含从最低值N到最高值（包括最高值）的所有数字，其中M1 个除外。
  2. 文件不必排序
  3. 这些值中只有 1 个缺失（只是确保）

那么解决方案就很简单了：

将文件中的所有数字相加或异或。
将您应该拥有的所有数字相加或异或。
缺少的数字要么是一个减去另一个（在 ADD 的情况下），要么是一个异或另一个。

这是一个您可以试验的LINQPad程序：

void Main()
{
    var input = new[] { 1, 2, 3, 4, 5, 6, 8, 9, 10 };

    var lowest = input[0];
    var highest = input[0];
    int xor = 0;
    foreach (var value in input)
    {
        lowest = Math.Min(lowest, value);
        highest = Math.Max(highest, value);
        xor ^= value;
    }
    int requiredXor = 0;
    for (int index = lowest; index <= highest; index++)
        requiredXor ^= index;

    var missing = xor ^ requiredXor;
    missing.Dump();
}

基本上，它将：

  1. 异或文件中的所有值（值 1）
  2. 同时找到最低和最高的数字
  3. 从最低到最高对所有值进行异或（值 2）
  4. 将两个值（值 1 和值 2）异或在一起以找到缺失值

此方法不会检测缺失值是最小值 - 1 还是最大值 + 1，例如，如果文件应该保存 1..10，但缺少 10 或 1，则上述方法将找不到它。

这个解决方案是 O(2n)（我们将数字循环两次），转换为 O(n)。

这是一个更完整的示例，显示了 ADD 和 XOR 解决方案（同样在 LINQPad 中）：

void Main()
{
    var input = new[] { 1, 2, 3, 4, 5, 6, 8, 9, 10 };
    MissingXOR(input).Dump("xor");
    MissingADD(input).Dump("add");
}

public static int MissingXOR(int[] input)
{
    var lowest = input[0];
    var highest = input[0];
    int xor = 0;
    foreach (var value in input)
    {
        lowest = Math.Min(lowest, value);
        highest = Math.Max(highest, value);
        xor ^= value;
    }
    int requiredXor = 0;
    for (int index = lowest; index <= highest; index++)
        requiredXor ^= index;

    return xor ^ requiredXor;
}

public static int MissingADD(int[] input)
{
    var lowest = input[0];
    var highest = input[0];
    int sum = 0;
    foreach (var value in input)
    {
        lowest = Math.Min(lowest, value);
        highest = Math.Max(highest, value);
        sum += value;
    }
    var sumToHighest = (highest * (highest + 1)) / 2;
    var sumToJustBelowLowest = (lowest * (lowest - 1)) / 2;
    int requiredSum =  sumToHighest - sumToJustBelowLowest;
    return requiredSum - sum;
}
于 2013-10-16T08:59:19.450 回答