Дан массив из n + 1 элемента, который содержит элементы от 1 до n и известно, что каждое число от 1 до n встречается хотя бы один раз. Предложите алгоритм, который находит дубликат за O(n) и O(1) дополнительной памяти.

задан 6 Апр 2:12

какая-нибудь сортировка не годится?...

(6 Апр 2:53) all_exist

@all_exist: а как Вы за время O(n) сможете отсортировать?

У меня другая идея была -- использовать алгоритм чьего-то имени (я англоязычные фамилии мгновенно забываю, к сожалению), который недавно в одном из вопросов обсуждался. Это где заяц и черепаха бежали. Схожая идея тут должна, скорее всего, работать, но надо её немного "доделать".

(6 Апр 3:11) falcao
1

a0 XOR a1 XOR ... XOR an XOR 1 XOR 2 ... XOR n.
Это вариация даже не задачи, а головоломки из студенческого фольклора.
В оригинальной постановке - из набора чисел и его копии убирают одно число. Найти за один проход убранное число.

(6 Апр 10:28) spades

@spades: а пи таком способе разве удаётся уложиться в ограничение на память O(1)? Или я не так понимаю символику?

(6 Апр 11:53) falcao

@falcao, а в чем проблема?
$%i:=1..n$%
$%\quad S = S\oplus a_i\oplus i$%
$%x = S\oplus a_{n+1}$%
Храним только $%S$%

(6 Апр 12:39) spades

@spades: при этом нам надо помнить "текущее" число S, но в памяти оно занимает порядка log n разрядов. Здесь же требуется константная память.

(6 Апр 14:26) falcao

@falcao, угу, я понял проблему. Но я сомневаюсь, что мы сможем вообще что-то сделать, если даже не сможем ни одно число из массива куда-либо сохранить. Да нам даже n хранить тогда негде... Думаю, все-таки, погрешность формулировки. Видимо, они отсекали вариант с n-битовым массивом.
Хотя, если честно, ничему не удивлюсь, если все же какой то фокус найдется. С этими алгоритмами вообще на "здравый смысл" нельзя полагаться

(6 Апр 14:32) spades

Ну давайте сыграем в дурачка. Сам массив то в памяти. Значит можно найти два наибольших его элемента, удалить, а освободившееся место использовать под свои нужды. Тем самым мы типа не используем лишнюю память.

(6 Апр 15:08) abc

То есть понятно, что в реальных условиях 64 бит выше крыши хватает, мы просто иначе перебрать даже не сможем, да и сам массив тогда где записан)) но формально мы не вписываемся. Если бы такие страхи были оправданы, то конкретно указывалось - не более 8 бит, например...
Другими словами неявно подразумевается, что n не превосходит разумных пределов: n < 2^32 и уж наверняка n < 2^64

(6 Апр 15:13) spades

@abc, @spades: по условию, у нас есть свободные ячейки памяти -- например, 10 штук. Там мы можем что-то хранить. Важно, чтобы это число ячеек не росло с увеличением n. Алгоритм с такими ограничениями, я думаю, должен существовать. Ср. недавнюю задачу нахождения периода последовательности (который она по условию имеет). Тут нечто похожее.

(6 Апр 15:13) falcao

Окей, у нас есть например 10 бит. И массив из 100000000 элементов от 1 до 100000000. Вопрос: как прочитать последний элемент массива, если его индекс не влезает в 10 бит?

(6 Апр 15:27) abc

@falcao, любой такой алгоритм проиграет представленному мною алгоритму как по скорости, так и по памяти любому реальному набору данных на практике. Зачем такие вещи предлагать?

(6 Апр 15:39) spades
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×237
×150

задан
6 Апр 2:12

показан
104 раза

обновлен
6 Апр 15:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru