задачка

[avva]

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

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

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

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

Comments

[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) нет, т.к. слишком большое число ;) см. здесь также.