Вроде бы так:

int cnt = 0;
int num;

for ( int i = 0; i < a.size(); ++i )
{
  if ( cnt > 0 && a[i] != num )
    --cnt;
  else
    ++cnt;

  if ( cnt == 1 )
    num = a[i];
}

ответ: num

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>>Здравствуйте Lexey, вы писали:

L>>>Сейчас вот пытаюсь обдумать такой вариант:
L>>>

L>>>int cnt=0;
L>>>for(int i=0;i<size_of_a;i++)
L>>>{
L>>>   if(!cnt) num=a[i];
L>>>   if(a[i]!=num) cnt--;
L>>>   else cnt++;
L>>>}
L>>>

АТ>>Такой вариант похоже действтельно будет работать.

АТ>... но несколько расточительно проверяет условия. Неоптимально. Более оптимальная реализация:

АТ>

АТ>int num;

АТ>for (unsigned i = 0; i < size_of_a; ++i)
АТ>{
АТ>  num = a[i];
АТ>  unsigned cnt = 1;

АТ>  for (++i; i < size_of_a; ++i)
АТ>    if (a[i] == num)
АТ>      ++cnt;
АТ>    else
АТ>      if (--cnt == 0)
АТ>        break;
АТ>}
АТ>

ОК. Тогда еще лучше так:

int num=a[0];
unsigned int cnt=1;
for (unsigned i = 1; i < size_of_a; ++i)
{
    if (a[i] == num)
      ++cnt;
    else
      if (--cnt == 0)
      {
         num=a[++i];
         cnt++;
      }
}

Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

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

F>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

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

F>Ходят слухи, что если массив целочисленный, то существует математическое
F>решение задачи. Но есть решение и в общем виде.

F>Что скажете?

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

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

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

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

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

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

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

_DA>>>Ее замечательно решили 5 лет назад.

H>>Но не дали доказательства правильности.

_DA>Хм. Решение:
_DA>Пробегаемся по массиву.
_DA>Если счетчик равен 0, то счетчику присваиваем 1, запоминаем число.
_DA>Иначе сравниваем число с запомненным. Если они равны, то увеличиваем счетчик на 1, иначе уменьшаем на 1.
_DA>После работы алгоритма мы получаем наше число, которое встречается в более половины значений в массиве.
_DA>Условие существования такого числа для некоторой последовательности обозначим (1).

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

Молодец, а тепрь смотрите мое сообщение от 10.06.06 20:19.

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

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

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

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

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

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

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

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

Здравствуйте, уважаемые. Хочу предложить вам поразмяться :-)

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

Ходят слухи, что если массив целочисленный, то существует математическое
решение задачи. Но есть решение и в общем виде.

Что скажете?

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

F>Здравствуйте, уважаемые. Хочу предложить вам поразмяться :-)

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

F>Ходят слухи, что если массив целочисленный, то существует математическое
F>решение задачи. Но есть решение и в общем виде.

Ну с целочисленным тут вроде все понятно. Создаешь массив счетчиков встречаемости конкретных чисел и запоминаешь текущий максимальный счетчик. Правда массив может получиться немерянного размера (2^32 для int, если нет никаких априорных ограничений на диапазон чисел). :)

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

Конечно, num не обязательно int. Можно поставить любой тип ( который можно сравнивать :) ).

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

V>Вроде бы так:

V>int cnt = 0;
V>int num;

V>for ( int i = 0; i < a.size(); ++i )
V>{
V> if ( cnt > 0 && a[i] != num )
V> --cnt;
V> else
V> ++cnt;

V> if ( cnt == 1 )
V> num = a[i];
V>}

V>ответ: num

По-моему, это лажа.
1) Чем ты "num" инициализировать будешь?
2) Имеем такую картину: всего есть 3k+1 элементов, принимающих всего 3 значения 0 — k+1 штук,1 — k штук,2 — k-штук.
В начале идут k нулей, затем k единиц, затем k двоек и в конце один 0. Такой алгоритм выдаст в итоге 2, а должен давать 0.

L>По-моему, это лажа.
L>1) Чем ты "num" инициализировать будешь?
L>2) Имеем такую картину: всего есть 3k+1 элементов, принимающих всего 3 значения 0 — k+1 штук,1 — k штук,2 — k-штук.
L>В начале идут k нулей, затем k единиц, затем k двоек и в конце один 0. Такой алгоритм выдаст в итоге 2, а должен давать 0.

Что то я не понял. Читаем условие задачи: "...Известно, что больше половины элементов
этого массива равны друг другу...". И какая "больше половины" элементов равны друг другу в твоём примере? Нулей вроде бы около одной трети.

num проинициализируется внутри цикла, т.к. кол-во элементов массива > 0.

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

L>>По-моему, это лажа.
L>>1) Чем ты "num" инициализировать будешь?
L>>2) Имеем такую картину: всего есть 3k+1 элементов, принимающих всего 3 значения 0 — k+1 штук,1 — k штук,2 — k-штук.
L>>В начале идут k нулей, затем k единиц, затем k двоек и в конце один 0. Такой алгоритм выдаст в итоге 2, а должен давать 0.

V>Что то я не понял. Читаем условие задачи: "...Известно, что больше половины элементов

Блин, посыпаю голову пеплом. Про больше половины я и не заметил. :(((

V>этого массива равны друг другу...". И какая "больше половины" элементов равны друг другу в твоём примере? Нулей вроде бы около одной трети.

V>num проинициализируется внутри цикла, т.к. кол-во элементов массива > 0.

Тоже логично.

А теперь и я посыпаю голову пеплом. :-)
В условии также сказано, что не разрешается создавать вспомогательные массивы.

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

F>А теперь и я посыпаю голову пеплом. :-)
F>В условии также сказано, что не разрешается создавать вспомогательные массивы.

Ну, в общем-то, то, что предложил Vitalische, не использует дополнительных массивов и действительно является требуемым решением. :)

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

V>Вроде бы так:

V>int cnt = 0;
V>int num;

V>for ( int i = 0; i < a.size(); ++i )
V>{
V> if ( cnt > 0 && a[i] != num )
V> --cnt;
V> else
V> ++cnt;

V> if ( cnt == 1 )
V> num = a[i];
V>}

V>ответ: num

Бессмыслица. Что-то вороде поиска самой длинной последовательности с лирическими отступлениями. Пойдет разве что как очень приближенный алгоритм. Не работает на { 3, 3, 1, 3, 3, 1, 3, 3, 2, 2, 2 }.

L>Ну, в общем-то, то, что предложил Vitalische, не использует дополнительных массивов и действительно является требуемым решением. :)

Не является он требуемым решением, ибо не работает.

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

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

F>>Ходят слухи, что если массив целочисленный, то существует математическое
F>>решение задачи. Но есть решение и в общем виде.

L>Ну с целочисленным тут вроде все понятно. Создаешь массив счетчиков встречаемости конкретных чисел и запоминаешь текущий максимальный счетчик. Правда массив может получиться немерянного размера (2^32 для int, если нет никаких априорных ограничений на диапазон чисел). :)

Не удовлетворяет условию задачи. Когда говорят "за один проход" имеется в виду — за O(N) операций. В твоем варианте понадобится порядка O(N) + O(M) операций, где M — длина массива счетчиков.

L>>Ну с целочисленным тут вроде все понятно. Создаешь массив счетчиков встречаемости конкретных чисел и запоминаешь текущий максимальный счетчик. Правда массив может получиться немерянного размера (2^32 для int, если нет никаких априорных ограничений на диапазон чисел). :)

АТ>Не удовлетворяет условию задачи. Когда говорят "за один проход" имеется в виду — за O(N) операций. В твоем варианте понадобится порядка O(N) + O(M) операций, где M — длина массива счетчиков.

Хм... Можно, конечно возразить, что O(M) — константа. В общем, теоретически ты прав. Полученный алгоритм действительно работает за O(N) и решает задачу. Но практически там вроде уже есть дополнительное условие о том, что дополнительные массивы заводить нельзя :)

Здравствуйте Андрей Тарасевич, вы писали:

АТ>Не удовлетворяет условию задачи. Когда говорят "за один проход" имеется в виду — за O(N) операций. В твоем варианте понадобится порядка O(N) + O(M) операций, где M — длина массива счетчиков.

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

Здравствуйте Андрей Тарасевич, вы писали:

L>>Ну, в общем-то, то, что предложил Vitalische, не использует дополнительных массивов и действительно является требуемым решением. :)

АТ>Не является он требуемым решением, ибо не работает.

Действительно не работает, но похоже, что это все-таки ошибка программирования, а не логики :)

Сейчас вот пытаюсь обдумать такой вариант:

int cnt=0;
type num=a[0];
for(int i=0;i<size_of_a;i++)
{
   if(a[i]!=num && cnt>0)
:cnt--;
   if(!cnt)
   {
       num=a[i];
   }
}

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

L>Здравствуйте Андрей Тарасевич, вы писали:

L>>>Ну, в общем-то, то, что предложил Vitalische, не использует дополнительных массивов и действительно является требуемым решением. :)

АТ>>Не является он требуемым решением, ибо не работает.

L>Действительно не работает, но похоже, что это все-таки ошибка программирования, а не логики :)

@#$%, блин. отправил раньше времени.


Сейчас вот пытаюсь обдумать такой вариант:

int cnt=0;
for(int i=0;i<size_of_a;i++)
{
   if(!cnt) num=a[i];
   if(a[i]!=num) cnt--;
   else cnt++;
}

Sorry, в программе ошибка (писал без компьютера );

int cnt = 0;
for ( int i = 0; i < a.size(); ++i ) 
{ 
  if ( cnt > 0 && a[i] != num ) 
    --cnt; 
  else 
  {
    ++cnt; 
   if ( cnt == 1 ) 
     num = a[i]; 
  } 
}

2 Андрей Тарасевич
>"Когда говорят "за один проход" имеется в виду — за O(N) операций. В твоем варианте понадобится порядка O(N) + O
>(M) операций, где M — длина массива счетчиков.".

Уважаемый "Brainbench C and C++ Programming MVP". Будьте добры разобраться в том, что написано, прежде чем писать о каком-то "массиве счетчиков", которого нет. Дополнительных массивов НЕТ. a[] — исходный массив с числами.

2Lexey.
По-моему, твой вариант будет работать. Решение короче и симпатичнее, чем у меня :)).

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

V>2 Андрей Тарасевич
>>"Когда говорят "за один проход" имеется в виду — за O(N) операций. В твоем варианте понадобится порядка O(N) + O(M) операций, где M — длина массива счетчиков.".
V>Уважаемый "Brainbench C and C++ Programming MVP". Будьте добры разобраться в том, что написано, прежде чем писать о каком-то "массиве счетчиков", которого нет. Дополнительных массивов НЕТ. a[] — исходный массив с числами.

Да ладно, не горячись. Это он про мой исходный вариант с дополнительным массивом написал. :)

V>2Lexey.
V>По-моему, твой вариант будет работать. Решение короче и симпатичнее, чем у меня :)).

Должен. Он получается из твоего, если if разбить на две части. :)

2 Андрей Тарасевич

Чёрт, каюсь и посыпаю голову пеплом. Сам не разобрался кто, кому и что написал. Ещё раз извиняюсь.

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

L>Ну давай еще поспорим. За один проход, может означать только именно за один проход по исходному массиву. Никаких других требований на сложность это не накладывает.

Ну ну ну! Если так подходить к требованию "за один проход", то тогда собственно и решать нечего: скопируй исходный массив в такой же отдельный массив (это делается за один проход), а затем уже делай все что угодно с копией. Хоть сто раз ее просматривай — все равно задача будет решена "за один проход" исходного массива...

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

F>Здравствуйте, уважаемые. Хочу предложить вам поразмяться :-)

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

F>Ходят слухи, что если массив целочисленный, то существует математическое
F>решение задачи. Но есть решение и в общем виде.

F>Что скажете?

Придумал. Правда массив надо будет преобразовать в список, но если этого не делать, то можно сформировать второй массив флажков.

Решение следующее:
Есть два указателя
1) на последний оставшийся элемент в массиве
2) на текущий элемент.

Если текущий и последний элемент не совпадают, то удаляем их из массива. Соответственно первый и второй указатель увеличиваем на еденицу или для списка смещаем вперёд.

Если текущий и последний элемент совпадают, то увеличиваем первый указатель на еденицу и сравниваем далее.

В итоге остаётся массив одинаковых элементов. Или пусто, если он не имел таковых.

Пример:

#- первый указатель
*- второй указатель
|- флажок

шаги:

для массивов для списка:

1)1 3 1 1 2 1 4 1 3 1 1 2 1 4
* # * #

2)1 3 1 1 2 1 4 1 1 2 1 4
| | * # * #

3)1 3 1 1 2 1 4 1 1 2 1 4
| | * # * #

4)1 3 1 1 2 1 4 1 1 4
| | | * | # * #

5)1 3 1 1 2 1 4 1 1 4
| | | * | # * #

6)1 3 1 1 2 1 4 1
| | | | | |

Всё. Надеюсь понятно объяснил. Для списка получается ровно один проход и сложность в элементарных операциях 4N(если правильно посчитал:)).

Для двух массивов один проход по первому массиву.

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

L>Сейчас вот пытаюсь обдумать такой вариант:
L>

L>int cnt=0;
L>for(int i=0;i<size_of_a;i++)
L>{
L>   if(!cnt) num=a[i];
L>   if(a[i]!=num) cnt--;
L>   else cnt++;
L>}
L>

Такой вариант похоже действтельно будет работать.

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

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

Блин. Пример криво отображается.
Привожу его есчо раз:


PSP>Пример:

PSP>#- первый указатель
PSP>*- второй указатель
PSP>|- флажок

PSP>шаги:

PSP>для массивов

PSP>1)1 3 1 1 2 1 4
PSP> * #

PSP>2)1 3 1 1 2 1 4
PSP> | | * #

PSP>3)1 3 1 1 2 1 4
PSP> | | * #

PSP>4)1 3 1 1 2 1 4
PSP> | | | * | #

PSP>5)1 3 1 1 2 1 4
PSP> | | | * | #

PSP>6)1 3 1 1 2 1 4
PSP> | | | | | |

для списка:
1)1 3 1 1 2 1 4
* #

2)1 1 2 1 4
* #

3)1 1 2 1 4
* #

4)1 1 4
* #

5)1 1 4
* #

6)1
The End

АТ>Здравствуйте Lexey, вы писали:

L>>Сейчас вот пытаюсь обдумать такой вариант:
L>>

L>>int cnt=0;
L>>for(int i=0;i<size_of_a;i++)
L>>{
L>>   if(!cnt) num=a[i];
L>>   if(a[i]!=num) cnt--;
L>>   else cnt++;
L>>}
L>>

АТ>Такой вариант похоже действтельно будет работать.

... но несколько расточительно проверяет условия. Неоптимально. Более оптимальная реализация:

int num;

for (unsigned i = 0; i < size_of_a; ++i)
{
  num = a[i];
  unsigned cnt = 1;

  for (++i; i < size_of_a; ++i)
    if (a[i] == num)
      ++cnt;
    else
      if (--cnt == 0)
        break;
}

Здравствуйте Андрей Тарасевич, Вы писали:

L>>Ну давай еще поспорим. За один проход, может означать только именно за один проход по исходному массиву. Никаких других требований на сложность это не накладывает.
АТ>Ну ну ну! Если так подходить к требованию "за один проход", то тогда собственно и решать нечего: скопируй исходный массив в такой же отдельный массив (это делается за один проход), а затем уже делай все что угодно с копией. Хоть сто раз ее просматривай — все равно задача будет решена "за один проход" исходного массива...

Ну давай только до такой степени не будем опошлять идею.

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте Lexey, вы писали:

L>>Сейчас вот пытаюсь обдумать такой вариант:
L>>

L>>int cnt=0;
L>>for(int i=0;i<size_of_a;i++)
L>>{
L>>   if(!cnt) num=a[i];
L>>   if(a[i]!=num) cnt--;
L>>   else cnt++;
L>>}
L>>

АТ>Такой вариант похоже действтельно будет работать.

АТ>А почему авторы алгортмов не приводят хотя бы схематического доказательства правильности?

Потому, что в облом. Доказательство "на пальцах" я в принипе придумал, а на придумывание строгого доказавательства времени жалко. :)

Разрешается ли перестраивать массив, если в ходе перестройки НЕ выполняются никакие вычисления ?

Разрешается ли перестраивать массив, если в ходе перестройки НЕ выполняются никакие вычисления ?

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

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

F>>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

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

F>>Ходят слухи, что если массив целочисленный, то существует математическое
F>>решение задачи. Но есть решение и в общем виде.

F>>Что скажете?

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

Супер! Стоило задачке 5 лет провисеть, чтобы ее наконец-то решили!

Кстати, таким способом можно не только, в массиве целых найти, можно в массиве любых объектов фиксированного размера, хоть в массиве структур. Его можно обощить и на случай массива с элементами переменной длины.

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

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

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

F>>>Здравствуйте, уважаемые. Хочу предложить вам поразмяться

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

F>>>Ходят слухи, что если массив целочисленный, то существует математическое
F>>>решение задачи. Но есть решение и в общем виде.

F>>>Что скажете?

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

V>Супер! Стоило задачке 5 лет провисеть, чтобы ее наконец-то решили!

Ее замечательно решили 5 лет назад.

V>Кстати, таким способом можно не только, в массиве целых найти, можно в массиве любых объектов фиксированного размера, хоть в массиве структур. Его можно обощить и на случай массива с элементами переменной длины.

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

_DA>Ее замечательно решили 5 лет назад.

Но не дали доказательства правильности.

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

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

_DA>>Ее замечательно решили 5 лет назад.

H>Но не дали доказательства правильности.

Хм. Решение:
Пробегаемся по массиву.
Если счетчик равен 0, то счетчику присваиваем 1, запоминаем число.
Иначе сравниваем число с запомненным. Если они равны, то увеличиваем счетчик на 1, иначе уменьшаем на 1.
После работы алгоритма мы получаем наше число, которое встречается в более половины значений в массиве.
Условие существования такого числа для некоторой последовательности обозначим (1).

Примерное доказательство:
Пусть известно, что среди чисел a1,...,ak выполняется условие (1) и счетчик никогда (за исключением начального состояния) не становится равен 0 при работе алгоритма. Тогда очевидно, что число, полученное в результате работы алгоритма, является ответом. И это число = a1.
Возьмем теперь некоторую последовательность b1,...,bn такую что в результате работы алгоритма на этой последовательности счетчик стал равен 0, и до этого нулю равен не был (2). Тогда очевидно, что b1 встречается в этой последовательности столько же раз, сколько и остальные числа.
Рассмотрим теперь последовательность b1,...,bn,a1,...,ak, для которой выполняется (1), а для b1,...,bn выполняется (2), то есть после первых n шагов получили счетчик, равный 0, тогда получаем, что в b1,...,bn искомое число встречается не более чем в половине случаев. Из этого следует, что a1,...,ak также удовлетворяет условию (1).
Таким образом все куски приводящие к обнулению счетчика можно отбрасывать и сводить задачу к задаче над остатком последовательности. Оставшийся кусок будет удовлетворять (1) и ответом будет первое число из этого куска.

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

H>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

А когда ситуация меняется?

Пусть N = 2M+1. И в наборе есть M+1 чисел "1", M чисел "2". То есть ответ "1".
И пусть в нашем наборе первые 2M чисел — это поочерёдно "1" и "2". То есть всё решается в последний момент.
Очевидно, что необходимо было запоминать двух лидеров.

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

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

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

H>>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые. Если лидер был искомым, то все равно в оставшейся части он должен встречаться больше половины. Задача сводится к той же, но уже начиная с текущего i. Если лидер был не искомым, то тем более. Если лидер никогда не менялся, то для каждого i он встречается больше всех остальных, вместе взятых, значит и для i=n, значит он и есть искомый.

К>А когда ситуация меняется?

К>Пусть N = 2M+1. И в наборе есть M+1 чисел "1", M чисел "2". То есть ответ "1".
К>И пусть в нашем наборе первые 2M чисел — это поочерёдно "1" и "2". То есть всё решается в последний момент.
К>Очевидно, что необходимо было запоминать двух лидеров.

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

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

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

Это не вяжется с твоим предуловием
H>>>Назовем num лидером и будем рассматривать ситуацию, когда лидер меняется. В этот момент лидер среди рассмотренных встречался столько же раз, сколько и все остальные вместе взятые.

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

К>>>Пусть мы рассмотрели первые 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>Чтрого говоря, так можно обойтись с любым бинарным представлением

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

Здравствуйте, 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>массиву выяснить чему же они равны.

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