задачка

[avva]

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

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

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

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

Comments

[avva.livejournal.com]

Неплохо, но:
1) можете ли доказать, что алгоритм всегда даёт правильный результат?
2) действительно ли тривиально расширить на нечётный размер? Напрашивается такой подход: отбросить один элемент, не являющийся самым частым, и свести задачу к чётному размеру; но можно ли легко найти такой элемент?

[dyak.livejournal.com]

2) Отбрасываем последний элемент и прогоняем алгоритм по первому прогону.
Если в счетчике >1, то идем на второй прогон как обычно.
Если в счетчике 0, то делаем кандидатом последний элемент и идем на второй прогон.
Конечно если не пользоваться введенными мною корявыми парами, то все проще.

[dyak.livejournal.com]

1) Если большевик (Б) есть, то все пары разбиваются на пары (Б,Б) в количестве Х1, пары (Б,неБ) и (неБ,Б) в количестве Х2 и прочие в количестве Х3, среди которых количество пар с одинаковыми членами равно Х4<=Х3.

Перевес Б над неБ в списке равен 2(Х2–Х3). Так как Х4<=Х3, то Х2 должно быть больше Х4.

Значит число пар (Б,Б) должно быть больше, чем других пар с одинаковыми членами.

На тех отрезках, где счетчик в конце 0, их не больше. Если в конце отрезок >0, то больше и есть только один кандидат.

Второй прогон определяет правоту гипотезы о кандидате грубой силой.

Если нечетное количество членов, то если счет 0, только последний может его размочить, значит он кандидат.
Если счет не 0, то перевес Б (если он есть) как минимум 2 и последний можно игорировать.