задачка

[avva]

Хорошая программистская задачка:

Дан список с данными. И есть подозрение, что более половины элементов в списке - это один и тот же элемент (число, например). Требуется определить, так ли это, и если так — то что это за элемент и сколько раз он встречается. За линейное время и без дополнительной памяти. (кроме константы).

Ссылку на журнал, из которого взял, дам позже, т.к. в нём есть решение.

P.S. Есть разные способы решения (я нашёл один из них, но не лучший, как потом узнал). Если из алгоритма неочевидно, что он всегда работает, нужно это доказать, иначе решение неполное.

Comments

[ex-ilyavinar899.livejournal.com]

Попытка решения: для простоты предположим, что число элементов чётное; расположим их по парам. Если два члена пары различны, то выбросить оба; иначе оставить один член из пары. После окончания шага (который займёт n/2 шагов) у нас будет максимум n/2 элементов. Лемма: если в исходном списке более 1/2 элементов имело одно значение, то в сокращённом списке будет так же. Потом сократить этот список еще вдвое (n/4 шагов), еще, и т. д. до списка из 1 элемента.

[french-man.livejournal.com]

Она же знаменитая задача про химиков - алхимиков из "Кванта":

http://kvant.mccme.ru/1979/09/zadachnik_kvanta_matematika.htm

[avva.livejournal.com]

Я наверняка торможу, но должен признаться, что не вижу эквивалентности этих задач. Можешь объяснить подробнее?

[french-man.livejournal.com]

Эквивалентности нет, но решать можно тем же способом.

Если твоих объектов четное число, разбиваешь их на пары, и называешь пару "хорошей" если входящие в нее объекты равны. Нехорошие пары выкидываются, а из каждой хорошей берется по представителю. Легко видеть, что в полученном м-ве представителей будет большинство однотипных объектов, если их было большинство в исходном м-ве. И.т.д.

Ситуация ухудшается, если исходных объектов - нечетное число. Тогда, при разбиении на пары, один придется выкинуть, и в новом м-ве однотипных может оказаться ровно половина. Но и в этом случае все вытанцовывается, хотя строгое решение слегка нудновато. (Я его писал много лет назад.)

Так же с химиками: разбиваешь на пары, спрашиваешь каждого о напарнике. Называешь пару "химической" если оба ответили, что напарник химик. Нехимические пары игнорируешь, из каждой химической берешь по представителю, и т.д. Так получется 2N-2 ответа. В твоей задаче - даже меньше, потому что для установления "хорошей" пары требуется одно сравнение, а для "химической" - два вопроса.

Но решение Дьяка (с модификацией Обломова) мне нравится больше. Хотя их алгоритм длиннее, его несколько проще запрограммировать.

[avva.livejournal.com]

Ага, теперь понятно, спасибо.