Наилучшая техника поиска для широкого диапазона входных данных

Question

Есть 1 миллиард номеров от 1 до 1 миллиарда, но отсутствует один номер.Все они доступны в случайном порядке, как найти недостающий наилучшим образом.

• случайно доступные средства означают, что они случайно распределены по всему массиву (т. Е. 5984,1,10937658, 20 ...)

Answer 1

Если проблема ограничена, Начните XORing каждого номера с самого начала. Затем XOR с 1 по 1B. Число, которое останется, является отсутствующим номером.

Примерно так:

Input-1 XOR Input-2 XOR Input-3 XOR Input-last XOR ... XOR 1 XOR 2 XOR...XOR 1B.

Если у вас достаточно памяти, сортируйте все числа и ищите последовательно.

Первый - O(N), второй - O(NlogN)

Пример меньшего набора:

1 xor 3 xor 1 xor 2 xor 3 => 2

Answer 2

Это только теоретические соображения, но если числа отсортированы 1,2,3...1B, так что вы можете просто разбить свою группу номеров на части 1 ... 0.5B и 0.5B ... 1B, тогда проверьте, сколько элементов в первой группе: если их меньше чем 0.5B элементов, что означает, что пропущенное значение находится между 1 и 0.5B, если есть 0.5B элементов, это означает, что пропущенное значение находится между 0.5B и 1B. Продолжайте процесс, пока не найдете пропущенное значение.

Я не знаю, является ли это очень быстрым способом, но он определенно быстрее, чем проверка каждого значения: D

Может быть, это ставит вас в путь