Найдите недостающее целое число на 32 бита среди неотсортированного массива, содержащего самое большее 4 миллиарда ints
Существуют бесплатные версии "Экспресса" Visual Studio. Учитывая, что Вам нравится Visual Studio и что выпуски "Экспресса" свободны, нет никакой причины использовать любого другого редактора.
6 ответов
Дополнительная информация на этом веб-сайте . Цитата оттуда:
«Полезно рассматривать этот двоичный поиск с точки зрения двадцати битов, которые представляют каждое целое число. На первом проходе алгоритма мы читаем (не более) один миллион входных целых чисел и записываем их с ведущий нулевой бит на одну ленту, а те, у которых один ведущий бит - на другую ленту. Одна из этих двух лент содержит не более 500000 целых чисел, поэтому мы затем используем эту ленту в качестве текущего входа и повторяем процесс проверки, но на этот раз на второй бит. Если исходная входная лента содержит N элементов, на первом проходе будет прочитано N целых чисел, на втором - не более N / 2, на третьем - не более N / 4 и т. д., поэтому общее время работы будет пропорционально N . Пропущенное целое число можно найти путем сортировки на ленте и последующего сканирования,
Общая идея такова: выберите диапазон целых чисел и выберите все целые числа, попадающие в этот диапазон. Если количество целых чисел меньше размера вашего диапазона, вы знаете, что этот диапазон содержит одно или несколько пропущенных чисел.
Это относится и к исходной проблеме, как вы знаете, что есть некоторые пропущенные числа в первую очередь.
Я полагаю, что автор имеет в виду, что вы выбираете середину текущего диапазона целых чисел и готовите два выходных файла. Когда вы читаете ввод, все, что находится выше средней точки, переходит в один файл, а все, что ниже средней точки, переходит в другой.
После этого вы выбираете, какой из файлов меньше, а затем повторяете операцию, используя [lower bound, midpoint] или (midpoint, upper bound] в качестве вашего нового диапазона, пока файл и диапазон не станут достаточно маленькими, чтобы переключиться на растровый образец (или один из ваших выходных файлов не станет пустым).
Damien
Если рассматривать числа в диапазоне от 1 до N; половина из них больше, чем N / 2, а половина из них меньше, чем N / 2
У тех, которые больше, чем N / 2, старший бит будет установлен в единицу; MSB = 0 for the smaller ones.
Partition the whole set based on MSB which will give you two sets : set of numbers smaller than N/2 and set of number larger than N/2
The partition smaller in size has the missing element.
In the next step, use the next MSB.
If the smaller set was less than N/2, half of them are less than N/4 (2nd MSB=0) and the other half larger than N/4 (2nd MSB=1)
If the smaller set was larger than N/2, half of them are less than N/2+N/4 (2nd MSB=0) and the other half larger than N/2+N/4 (2nd MSB=1)
Each round will halve the search space and that's it.
Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)
This is basically the same question as this question. The same approach works here for the ample memory case to get O(N) complexity. Basically just recursively try to put every integer to its correct location and see what doesn't have the correct value.
Ну, это о файле, который содержит все 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. QED