задачка

[avva]

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

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

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

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

Comments

[oblomov-jerusal.livejournal.com]

А разве это не очевидно из записи dyak? Пусть некий элемент содержится в списке с частотой более 50%. Если в списке идут подряд два различных элемента, то после их удаления данное свойство списка сохранится. Повторяя эту операцию с произвольным списком, мы в конце концов придем к списку, содержащему лишь одно значение (или к пустому списку). Такой список можно представить значением элемента и длиной списка. Алгоритм последовательно вычисляет такой редуцированный список для каждого начального отрезка списка.

[avva.livejournal.com]

Начальный отрезок списка вовсе необязательно обладает тем свойством, что в нём некий элемент содержится с частотой более 50%. Поэтому неясно, что алгоритм вычисляет для такого начального отрезка, и как это ему помогает в будущем. Мне кажется, что Ваш аргумент верен только для списков, в которых пары различных элементов всегда можно отбрасывать с конца.

[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).