Найти недостающее 32-битное целое число среди несортированного массива, содержащего не более 4 миллиардов целых
Это проблема, описанная в Programming pearls, Я не могу понять метод двоичного поиска, описанный автором. Может кто-нибудь поможет уточнить? Благодарю.
РЕДАКТИРОВАТЬ: я могу понять бинарный поиск в целом. Я просто не могу понять, как применить бинарный поиск в этом особом случае. Как решить, что пропущенный номер находится в некотором диапазоне или нет, чтобы мы могли выбрать другой. Английский не мой родной язык, поэтому я не могу понять автора. Итак, используйте простой английский, пожалуйста:)
РЕДАКТИРОВАТЬ: Спасибо всем за ваш отличный ответ и комментарии! Самый важный урок, который я извлек из решения этого вопроса, заключается в том, что бинарный поиск применяется не только к отсортированному массиву!
6 ответов
На этом сайте есть еще немного информации. Цитируется оттуда:
"Полезно рассматривать этот двоичный поиск в терминах двадцати битов, представляющих каждое целое число. На первом проходе алгоритма мы читаем (не более) миллиона входных целых чисел и записываем те, у которых начальный нулевой бит находится на одной ленте, и те, у которых один ведущий бит переходит на другую ленту. Одна из этих двух лент содержит не более 500000 целых чисел, поэтому мы затем используем эту ленту в качестве текущего ввода и повторяем процесс проверки, но на этот раз для второго бита. Если исходная лента ввода содержит N элементов, первый проход будет читать N целых чисел, второй проход не более N/2, третий проход не более N/4 и т. д., поэтому общее время выполнения пропорционально N. Пропущенное целое число может быть найдено путем сортировки на ленте и последующего сканирования, но для этого потребуется время, пропорциональное N log N ".
Как видите, это разновидность алгоритма бинарного поиска: разделите задачу на две части и решите проблему для одной из меньших частей.
Общая идея такова: выберите диапазон целых чисел и выберите все целые числа, попадающие в этот диапазон. Если число целых чисел меньше размера вашего диапазона, вы знаете, что этот диапазон содержит одно или несколько пропущенных чисел.
Это относится и к первоначальной проблеме: откуда вы знаете, что в первую очередь есть пропущенные числа?
Я полагаю, что автор достиг того, что вы выбрали середину текущего диапазона целых чисел и подготовили два выходных файла. Когда вы читаете ввод, все, что выше средней точки, переходит в один файл, а все, что ниже средней точки, переходит в другой.
По завершении вы выбираете, какой из файлов меньше, а затем повторяете операцию, используя [нижнюю границу, среднюю точку] или (среднюю точку, верхнюю границу] в качестве нового диапазона, пока файл и диапазон не станут достаточно маленькими, чтобы переключиться на растровый шаблон (или один из ваших выходных файлов пуст).
Damien
Это в основном тот же вопрос, что и этот вопрос. Тот же подход работает здесь для случая достаточного объема памяти, чтобы получить сложность O(N). В основном просто рекурсивно попробуйте поместить каждое целое число в правильное местоположение и посмотреть, что не имеет правильного значения.
Если учесть числа в диапазоне от 1 до N; половина из них больше, чем N / 2, а половина из них меньше, чем N / 2
Для тех, которые больше, чем N / 2, MSB будет установлен в единицу; MSB = 0 для меньших.
Разбейте весь набор на основе MSB, который даст вам два набора: набор чисел, меньших, чем N / 2, и набор чисел, больших, чем N / 2.
Раздел меньшего размера имеет отсутствующий элемент.
На следующем шаге используйте следующий MSB.
Если меньший набор был меньше, чем N / 2, половина из них меньше, чем N/4 (2-й MSB=0), а другая половина больше, чем N/4 (2-й MSB=1)
Если меньший набор был больше, чем N / 2, половина из них меньше, чем N/2+N/4 (2-й MSB=0), а другая половина больше, чем N/2+N/4 (2-й MSB=1)
Каждый раунд сократит пространство поиска вдвое и все.
Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)
Ну, это о файле, который содержит все 4 миллиарда целых, кроме одного! Это подвох в этом случае.
- По мере перемещения по списку целых чисел, рассчитать сумму.
- В конце вычислите сумму, как если бы присутствовали все целые числа, используя формулу N * (N + 1) / 2.
- Извлеките сумму в (1) из суммы, которую вы вычислили в (2). Это недостающее целое число.
Пример. Предположим, у нас следующая последовательность: 9 3 2 8 4 10 6 1 7 (от 1 до 10 с 5 пропущенными). Когда мы последовательно добавляем целые числа, мы получаем 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50. Сумма всех целых чисел от 1 до 10 будет 10 * (10 + 1) / 2 = 55 Следовательно, пропущенное целое число равно 55 - 50 = 5. КЭД