Здравствуйте, Кодт, Вы писали:

К>>>Пусть мы рассмотрели первые K (K < N/2) элементов, и они все разные. Кто лидер? Придётся запоминать их всех.

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

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Кодт, Вы писали:

К>>>>Пусть мы рассмотрели первые K (K < N/2) элементов, и они все разные. Кто лидер? Придётся запоминать их всех.

E>Это должно обозначать одно из двух.
E>Или массив не обладает заявленным свойством, или лидер оставшейся части массива таки совпадает с лидером всего массива.
E>В первом случае никто ничего не обещал, во втором не важно кто лидер на этом этапе. Всё равно надо начинать искать лидера с нуля, но уже только в оставшейся части массива.
Совершенно верно. Это было в моем решении.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, lxa, Вы писали:

lxa>>Для целочисленного массива, допустим это n (32, 64) — битные integer. Пробегаемся по массиву и считаем, сколько раз каждый бит (1) попадается. Потом составляем по биту искомое число — если вероятность 1 на этой позиции больше 0.5, ставим 1, иначе 0.

E>Чтрого говоря, так можно обойтись с любым бинарным представлением

А если у некого объекта несколько разных бинарных представлений?

Здравствуйте, Dmi_3, Вы писали:

D_>А если у некого объекта несколько разных бинарных представлений?
Понятно, с чем не согласен! Спасибо!

Короче говоря, тогда можно стандартизировать бинарное представление этого объекта.
Ну выбрать какое-то одно, при проходе массива для каждого объекта такое представление вычислять, и потом вычислять по нему статистику

Правда всё равно могут быть проблемы, но с double вроде как должно получиться

Здравствуйте, _DAle_, Вы писали:

_DA>Примерное доказательство:

[Много букв... не осилил]

По-моему, надо строить доказательство от более высокоуровневой логики. Я в доказательствах не силен, но вот примерная схема. Если количество искомых элементов строго больше половины, значит как минимум два таких элемента следуют подряд (если данное утверждение и нуждается в доказательстве, то оно должно быть простым). Значит, всегда имеется непрерывная последовательность как мининимум из двух искомых элементов. Далее надо доказать для общего случая — что непрерывная последовательность из искомых элементов обязана быть самой длинной из всех прочих. Ну а найти эту последовательность — задача тривиальная. Собственно, приведенный пять лет назад алгоритм именно это и делает.

Здравствуйте, McSeem2, Вы писали:

MS> Далее надо доказать для общего случая — что непрерывная последовательность из искомых элементов обязана быть самой длинной из всех прочих.

Контрпример: AA B AA B AA B CCC

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, _DAle_, Вы писали:

_DA>>Примерное доказательство:

MS>Далее надо доказать для общего случая — что непрерывная последовательность из искомых элементов обязана быть самой длинной из всех прочих.

Контрпример — 1, 1, 0, 0, 0, 1, 1

По предложенному тобой алгоритму правильный ответ — 0. А на самом деле 1.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, _DAle_, Вы писали:

_DA>>Примерное доказательство:

MS>[Много букв... не осилил]

MS>По-моему, надо строить доказательство от более высокоуровневой логики. Я в доказательствах не силен, но вот примерная схема. Если количество искомых элементов строго больше половины, значит как минимум два таких элемента следуют подряд (если данное утверждение и нуждается в доказательстве, то оно должно быть простым). Значит, всегда имеется непрерывная последовательность как мининимум из двух искомых элементов. Далее надо доказать для общего случая — что непрерывная последовательность из искомых элементов обязана быть самой длинной из всех прочих. Ну а найти эту последовательность — задача тривиальная. Собственно, приведенный пять лет назад алгоритм именно это и делает.

Жирным выделены неверные утверждения. Контрпример для обоих: 101.

Здравствуйте, serge_levin, Вы писали:

_>Контрпример — 1, 1, 0, 0, 0, 1, 1
_>По предложенному тобой алгоритму правильный ответ — 0. А на самом деле 1.

Нет, по предложенному алгоритму как раз ответ 1.
Простоон ищет вовсе и не самую длинную подпоследовательность одинаковых элементов

Здравствуйте, fearless, Вы писали:

F>Есть массив длинны N. Известно, что больше половины элементов
F>этого массива равны друг другу. Требуется за один (!) проход по
F>массиву выяснить чему же они равны.

Если за один просмотр предполакает конечный автомат, то задача не решается по леме о разрастании.