можно ли модифицировать список данных (сортировать)?

Всё равно ведь невозможно отсортировать за линейное время.
Но в принципе в условии задачи не сказано, можно ли модифицировать список. Ясно, что лучше обойтись без модификации, но я не скажу, можно без неё обойтись или нельзя ;)

Нельзя ли уточнить, что значит "без дополнительной памяти. (кроме константы)." Константным подразумевается число дополнительных переменных или ничем кроме исходного массива и некоей константы нельзя пользоваться? Или нечто иное?

Размер дополнительной памяти, которой можно пользоваться - константа, т.е. не зависит от размера исходного списка. Это может быть какое-то фиксированное число дополнительных переменных, или дополнительный массив фиксированного размера, итп.

Если такое число существует, то оно median (как оно по-русски называется?). Говорят (в сети), что есть линейный метод нахождения median. Находим (за линейное время) и проверяем (также за линейное время).

Остроумно! ;-)

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

Сумма квадратична, извините.

Еще уточнение, если не затруднит: для элементов списка существуют операции "больше"/"меньше"? или только "равно"?

Можно делать больше/меньше при желании.

Для четного количества в списке.
Если разделить список на пары, то если член "х" –– большинство, то, если искомый член "х" есть, то, если пары, где члены разные, повыкидывать, то
число пар, где оба члена –– "х" должно быть больше, чем число пар, где оба члена –– "не х". Как предельный случай можно поиграть со списком их а+1 белых и а–1 черных.

Значит действуем так: игнорируем все смешанные пары и ставим счетчик на 0. Идем до первой одинаковой пары, замечаем ее члены как кандидата на большинство, ставим счетчик на 1. Если следующая одинаковая пара такая же, то увеличиваем счетчик на 1, если она другая, вычитаем из счетчика 1. Если счетчик оказывается на 0, то следующая одинаковая пара дает нам кандидата и 1 в счетчике.

В процессе узнаем сколько членов в списке.

Если в конце процесса имеем не 0 в счетчике и кандидата, то на следующем прогоне считаем сколько найдем кандидата в списке. Если >50%, ура.

На нечетное число членов тривиально распространимо, но писать лень.

А сколько потребуется "прогонов" в самом худшем случае?

Я намеренно не смотрю на остальные комментарии.

Одно слово: хэширование.

Hash is not deterministic - what if all the values are in the same bucket?

Если на элементах задана операция сравнения и разрешается переупорядочивать список, то легко модифицировать стандартный алгоритм поиска элемента. Выбираем случайный элемент a, проходим по списку, составляем 2 списка: больших a и меньших или равных a. Выбираем больший из двух списков и продолжаем с ним работать. Если хотим детерминистский алгоритм, то из каждых 5 элементов выбираем медианный, находим медиану всех выбранных, и найденный элемент используем как a(OK, это уже не постоянная память)

Пусть элемент представлен строкой в k бит. Проходим по списку, считаем, сколько раз встречается старший бит 0. Выбираем тот, что встречается чаще. На шагу i мы имеем i-1 старших бит элемента, и мы проходим по списку и считаем, сколько раз встречается 0 и 1 после этих i-1 бит, и определяем на основе подсчета бит i. (естественно, вместо бита можем пользоваться более крупной единицей, напр. байтом).

Да, так тоже можно.

2 prohoda vdol' spiska.
Voz'mem nebol'shoj massiv (naprimer 10 elementov). Kazhdyj element massiva - para: element-chastota elementa. Budem zapisyvat' v nego elementi po mere postuplenia a zaodno i schitat' ih kolichestvo (chastotu). Kak tol'ko nam vstretit'sja 11-i element, nachnem zapolnjat' vtoroj takoj zhe massiv. Kogda vtoroj massiv okazhetsja zapolnennym, soljem dva massiva v odin, t.e. vyberem iz 20 elementov 10 s maksimal'nymi chastotami. Ochistim vtoroj massiv i stanem zapolnjat' ego snova, poka nam opjat' ne popadetsja 11-i element. Opjat' soljem 2 massiva (ili viberem 10 maksimalnih) i t.d. V konce u nas budet iskomyj element odnim iz 10 v pervom massive. Teper' delaem eshe odin prohod, podschityvaja chastoty tol'ko etih 10 elementov - i togda u nas budet okonchatel'nyj otvet.
Vozmozhno 10 elementov - dazhe bol'she chem nuzhno. Vpolne verojatno 2-3 dostatochno.
Algoritm rabotaet, dazhe esli elementy - ne chisla i predstavit' ih v vide korotkoj stroki ne predstavljaetsja vozmozhnym.
Ne znaju poka kak obosnovat', no dumaju chto esli element zanimaet bol'she poloviny spiska, to ego nevozmozhno raspredeli't po spisku takim obrazom, chtobi on ne popal v okonchatel'nyj massiv.

Есть у меня вот какое бездоказательное подозрение.

Для удобства рассмотрим этот список как кольцо (мысленно замкнем начало с концом). Если значение X встречается больше чем в 50% элементов, то в кольце обязательно будут последовательности подряд идущих X-ов, причем длина максимальной такой цепочки будет больше всех других последовательностей подряд идущих одинаковых элементов.

За один проход находим максимальную цепочку одинаковых значений X, за второй - убеждаемся, действительно ли X-ов больше 60% в списке.

Ooops, не работает :(

Любимая моя задачка про инварианты: если выкинуть два любых различных элемента, то решение новой задачи совпадает с решением исходной.

ык... упрощeнный коррeляционный фильтр.

Гeнeрируются случайная послeдоватeльность ( можно - по кругу, eсли выборка конeчная - с остатком от дeлeния по модулю N ) с попарным
сравнeниeм номeров, совпали + 1, нe совпали: -1, вeдeм сумму и сравниваeм с заранee выбранной константой...

У меня есть подозрение, что если одно значение составляет больше половины элементов списка, то у него будут самая длинная последовательность, состоящая из одного значения.

У меня есть подозрение, что если одно значение составляет больше половины элементов списка, то у него будут самая длинная последовательность, состоящая из одного значения.

Нет:

1 1 1 2 2 3 2 2 3 2 2 3 2 2 3

Скоро напишу отдельную запись.