задачка

[avva]

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

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

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

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

Comments

[shulga.livejournal.com]

Как ни крути, хоть медианы, хоть побитная проверка - всё одно и тоже.
Если объекты однобитные +1 и -1, тогда N if'ов и N операций (например, суммирования).
IFы нужны, собственно, если они НЕ +1 и -1.
Если битов в объекте K, тогда в К раз больше работы.
Предполагается простейший набор команд процессора.