задачка

[avva]

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

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

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

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

Comments

[oblomov-jerusal.livejournal.com]

Пусть элемент представлен строкой в k бит. Проходим по списку, считаем, сколько раз встречается старший бит 0. Выбираем тот, что встречается чаще. На шагу i мы имеем i-1 старших бит элемента, и мы проходим по списку и считаем, сколько раз встречается 0 и 1 после этих i-1 бит, и определяем на основе подсчета бит i. (естественно, вместо бита можем пользоваться более крупной единицей, напр. байтом).

[avva.livejournal.com]

Да, так тоже можно.

[mi-b.livejournal.com]

это дает сложность O(n log(n)) если число элементов n=O(exp(k))

[avva.livejournal.com]

А разве не O(n*const), где умножаем на фиксированное число битов в представлении элемента? Или я что-то не так понял? Мне показалось, что мы просто делаем k проходов всего массива, где k - это фиксированное число.

[mi-b.livejournal.com]

Если для вас k константа, то exp(k) тоже константа;). Значит, можно завести exp(k) счетчиков. За один проход по списку заполняем счетчики, затем за exp(k)=const время ищем максимальный счетчик. Соответственно, в этой формулировке задача тривиальна, а интересна и естественна задача, когда k = O(log(n)).

[avva.livejournal.com]

Если для вас k константа, то exp(k) тоже константа;).

Ну как Вам сказать ;) для меня k константа, а exp(k) нет, т.к. слишком большое число ;) см. здесь также.

улучшение, вроде

[(Anonymous)]

достаточно пройти один раз, независимо подсчитывая число единиц для каждого i-ого бита (т.е посчитать независимые суммы в i-ом разряде), и заодно число элелемтов в списке. после этого формируем число-кандидат так: его i-ый разряд равен 1, если единиц в этом разряде в списке было большинство, или 0 иначе.
Если в каком-то разряде единиц и нулей было поровну, то искомого числа нет.

И проверяем число-кандидат вторым проходом по списку.

[avva.livejournal.com]

Да, действительно, спасибо!

Re: улучшение, вроде

[oblomov-jerusal.livejournal.com]

дв