Программирование Pearls: поиск недостающего целого числа в файле из 4 миллиардов целых чисел

Question

Вопрос: вход находится в последовательном файле. Файл содержит не более 4 миллиардов целых чисел. Найдите пропущенное целое число.

Решение согласно моему пониманию:

1. сделать два временных файла, один с первым 0, а другой с первым 1

2. один из двух ДОЛЖЕН быть (голубиные отверстия 4.3B и голуби 4B) ​​меньше 2B. Выберите файл и повторите шаги 1 и 2 для 2-го бита, а затем для 3-го бита и т. Д.

каково конечное условие этой итерации?

Кроме того, в книге упоминается эффективность алгоритма O(n), но,

1-я итерация => n пробных операций
2-я итерация => n/2 пробных операций
,
,
,
n + n/2 + n/4 +... 1 => nlogn??

Я что-то пропустил?

Answer 1

Если пропущено только 1 значение, это означает, что у вас есть следующие критерии:

1. Файл содержит все числа в диапазоне от минимального значения, N вплоть до самой высокой стоимости, Mкроме одного из этих номеров.
2. Файл не должен быть отсортирован
3. Отсутствует только 1 из этих значений (просто убедитесь)

Тогда решение довольно простое:

ДОБАВЬТЕ или XOR вместе все числа в файле.
ДОБАВЬТЕ или XOR вместе все числа, которые вы должны иметь.
Отсутствующее число - либо один минус другой (в случае ДОБАВЛЕНИЯ), либо один или другой.

Вот программа 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. XOR все значения в файле вместе (значение 1)
2. Найти самые низкие и самые высокие цифры одновременно
3. XOR все значения от низшего к высшему (значение 2)
4. XOR два значения (значение 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;
}

Answer 2

Вы проверите оба файла и выберете один с наименьшим количеством элементов.

Вы будете повторять этот процесс до тех пор, пока не пройдете все 32 бита, и в конце у вас будет файл 0 элементов. Вот где должен был быть один из пропущенных номеров. Итак, если вы отслеживали биты, которые отфильтровали до сих пор, вы будете знать, каким должно быть число.

Обратите внимание, что это для того, чтобы найти (то есть "любое") пропущенное число. Если дан (неупорядоченный) последовательный список из 4 миллиардов (не 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