Сложный вопрос об алгоритме [дубликат]

На этот вопрос уже есть ответы здесь :

Закрыто 9 лет назад .

Возможный дубликат:
Самый быстрый способ найти отсутствующее число в массиве чисел

Ввод: несортированный массив A [1, .., n], который содержит все целые числа в диапазоне, кроме одного. 0, .., n

Проблема состоит в том, чтобы определить отсутствующее целое число за время O (n). Каждый элемент A равен представлен в двоичном формате, и единственная доступная операция - это бит функции (i, j), который возвращает значение j-го бита A [i] и занимает постоянное время.

Есть идеи? Я думаю, что какой-то алгоритм «разделяй и властвуй» был бы подходящим, но я не могу придумать, что именно мне следует делать. Заранее спасибо!

задан Community 23 May 2017 в 11:50

0 ответов

Другие вопросы по тегам:

algorithm puzzle divide-and-conquer

Сложный вопрос об алгоритме [дубликат]

0 ответов

Похожие вопросы: