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

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

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

Что скажете?

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

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

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

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

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

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

Вроде бы так:

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

Конечно, 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>Ну давай еще поспорим. За один проход, может означать только именно за один проход по исходному массиву. Никаких других требований на сложность это не накладывает.

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