задачка

[avva]

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

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

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

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

Comments

[oblomov-jerusal.livejournal.com]

Мы определяем операцию редукции как удаление из списка пары последовательныз различных значений. Для каждого начального отрезка алгоритм вычисляет один из возможных результатов многократного применения операции редукции. Если список x можно редуцировать к списку >a;<**N, где N>0 то список x.<a;> можно редуцировать к списку <a>**(N+1), а список x.<b>, где b≠a, - к списку <a>**(N-1) - это шаг алгоритма. Если x можно редуцировать к пустому списку, то x.<a> можно редуцировать к <a>**1. Результат редукции, вообще говоря, неоднозначен, например 1,2,3,1 можно редуцировать к 1,1 или к пустому списку. Но если значение a встречается в списке с частотой более 50%, то тем же свойством будет обладать и редуцированный список, т.к. операция редукции сохраняет это свойство.

[avva.livejournal.com]

Да, согласен, спасибо. Моё док-во было длиннее, т.к. я сначала показал, что при наличнии элемента с частотой >50% исходный список можно свести к списку с двумя элементами (объединив все остальные элементы в один). В списке из двух элементов результат редукции всегда однозначен, поэтому мне казалось, что индукция будет проще; но теперь я вижу, что и без этого просто.

[oblomov-jerusal.livejournal.com]

А если рассмотреть операцию выбрасывания k элементов с различными значениями (не обязательно соседних) то можно получить способ нахождения элементов встречающихся с частотой не менее 1/k за время O(kn) с дополнительной памятью O(k).