static void Main(string[] args)
{
int[] source =
//{ 2, 8, 2, 8, 2, 8, 2 };
//{ 2, 2, 2, 8, 8, 8, 2 };
{ 2, 2, 2, 8, 8 };
List<int> list = new List<int>();
list.AddRange(source);
while (list.Count > 1)
{
ProcessItemPairs(list);
}
if (list.Count == 0)
Console.WriteLine("Нет решения");
else
Console.WriteLine(list[0]);
}
static void ProcessItemPairs(List<int> values)
{
for (int i = values.Count - 2; i >= 0; i -=2 )
{
int j = i + 1;
if (values == values[j])
values.RemoveAt(j);
else
{
values.RemoveAt(j);
values.RemoveAt(i);
}
}
}
Найти доминирующий елемент в масиве (алгоритм)
Задачу задали моему другу на собеседовании в одной более чем извесной фирме. Ответ он дал не самый оптимальный, а я так вообще облажался. Так что и задачу и ответ мне розказали. Думаю вам может быть интересно.
Есть одномерный масив. Извесно что в нем есть доминирующий елемент (тоесть елемент который встречается больше чем в половине ячеек масива). Нужно его найти за минимальную сложность.
Пример: Масив - 1 2 2 2 3 2 Ответ - 2 (потому что 2 встеречаеется более 3-х раз).
Есть одномерный масив. Извесно что в нем есть доминирующий елемент (тоесть елемент который встречается больше чем в половине ячеек масива). Нужно его найти за минимальную сложность.
Пример: Масив - 1 2 2 2 3 2 Ответ - 2 (потому что 2 встеречаеется более 3-х раз).
Помнится решал такую задачку на школьной олимпиаде по информатике. Тогда решил ее далеко не самым оптимальным способом, но зато быстрым :)
Спасло тогда то, что на элементы массива стояло ограничение от 1 до 1000. Тогда я просто объявил один большой разряженный массив от 1 до 1000 и по мере считывания из файла чисел элемент этого массива с индексом равным считанному числу увеличивал на 1 и запоминал этот индекс, если полученное после увеличения значение было больше уже существующего максимального.
Бред конечно. :) Но все тесты решение прошло на ура. Хорошо что на олимпиадах исходники не смотрят.
Изучив через пару недель класс std::map, понял, что тоже самое можно было сделать с его помощью. Тогда бы решение было не столь требовательно к памяти, да и большие ограничения были бы не помеха, хотя и чуть медленее.
Спасло тогда то, что на элементы массива стояло ограничение от 1 до 1000. Тогда я просто объявил один большой разряженный массив от 1 до 1000 и по мере считывания из файла чисел элемент этого массива с индексом равным считанному числу увеличивал на 1 и запоминал этот индекс, если полученное после увеличения значение было больше уже существующего максимального.
Бред конечно. :) Но все тесты решение прошло на ура. Хорошо что на олимпиадах исходники не смотрят.
Изучив через пару недель класс std::map, понял, что тоже самое можно было сделать с его помощью. Тогда бы решение было не столь требовательно к памяти, да и большие ограничения были бы не помеха, хотя и чуть медленее.
Цитата: Rebbit
(тоесть елемент который встречается больше чем в половине ячеек масива)
Интересная подробность :)
Тогда можно:
1. отсортировать массив,
2. считать число цифр до перехода от одной цифры к другой,
3. если количество меньше половины всех цифр - вернуться к п.2
4. выдать результат - число, количество которых больше чем половина количества всех цифр.
Примерно так :)
Цитата: Kogrom
1. отсортировать массив,
2. считать число цифр до перехода от одной цифры к другой,
3. если количество меньше половины всех цифр - вернуться к п.2
4. выдать результат - число, количество которых больше чем половина количества всех цифр.
Не самый оптимальный вариант, но вполне жызнеспособный.
Тут вся нагрузка пойдет на сортирование. Получим N log(N) (хотя можно и поспорить но в общем случае будет такая сложность ).
Относительно пунктов 2 - 4. Их можно сильно соптимизировать. Оч сильно. :)
ЗЫ. А вообще не факт что масив получится отсортировать. По большому щету операции <, > могут быть неопределены для елементов масива, но пока пусть елементами будут целые числа.
Цитата:
тоесть елемент который встречается больше чем в половине ячеек масива
- Есть алгоритм поиска порядковой статистике. В данном случии медианы.
http://en.wikipedia.org/wiki/BFPRT
Пословам это быстрее сортировки.
Цитата: Pavia
- Есть алгоритм поиска порядковой статистике. В данном случии медианы.
Пословам это быстрее сортировки.
Пословам это быстрее сортировки.
К сожалению в статистике я полный 0 :(.
Но уверен что оптимальный алгоритм быстрее.
Быстрее O(n)?
Цитата: Rebbit
Относительно пунктов 2 - 4. Их можно сильно соптимизировать. Оч сильно. :)
Ну, можно просуммировать по половинам и поделить на количество половины. Потом поискать пару чисел в каждой из половин, которые с результатом совпадут.
А вообще... Смутно представляется алгоритм в котором сравниваем все числа с соседним, а последнее с первым. Если нет равенства, то убираем число из массива, из следующей итерации сравнений. В каждой итерации смотрим были ли убраны числа. Когда перестанут убираться - останутся только доминирующие...
ЗАчем после сортировки наиболее часто встречающийся элемент будет по середине массива. Но еще раз повторяю можно без сортировки гораздо быстрее сделать за линейное время.
Цитата: Pavia
ЗАчем после сортировки наиболее часто встречающийся элемент будет по середине массива.
да. Туплю :)
Если решать "в лоб", тогда наверное самое простое два цикла (один вложен в другой), только циклы вести не по всей длине массива а лишь для (n/2 + 1) элементов, при этом отсеивая из массива уже проверенные элементы.
Ну здесь кажется и за O(n/2) решить можно. По крайней мере, первый шаг - сравнивать элементы непересекающимися парами.
Цитата: Pavia
повторяю можно без сортировки гораздо быстрее сделать за линейное время.
Ето той порядковой статистикой ? Сори за тупой вопрос. Я просто не успел еще в нее посмотреть толком.
Цитата: Der Meister
Ну здесь кажется и за O(n/2) решить можно. По крайней мере, первый шаг - сравнивать элементы непересекающимися парами.
Ыыы.... Туплю с утра. Можно подробнее ?
Цитата: Der Meister
Ну здесь кажется и за O(n/2) решить можно. По крайней мере, первый шаг - сравнивать элементы непересекающимися парами.
Черновой (и не отлаженный) вариант пока таков:
Код:
Цитата: Der Meister
Черновой (и не отлаженный) вариант пока таков:
Похоже на правду.
Я не запускал, но кажись входы
8 8 2 2 2
8 8 2 2 2 2
не пройдут ??
ЗЫ и сложность тут будет не N/2 а N (Точнее N-1 в худшем случае)
Цитата: Rebbit
Похоже на правду.
Я не запускал, но кажись входы
8 8 2 2 2
8 8 2 2 2 2
не пройдут ??
ЗЫ и сложность тут будет не N/2 а N (Точнее N-1 в худшем случае)
Я не запускал, но кажись входы
8 8 2 2 2
8 8 2 2 2 2
не пройдут ??
ЗЫ и сложность тут будет не N/2 а N (Точнее N-1 в худшем случае)
Так какое же правильное решение?
[QUOTE=Rebbit]Я не запускал, но кажись входы
8 8 2 2 2
8 8 2 2 2 2[/QUOTE]Есть такое, надо учитывать чётность количества элементов. Остаточный, необработанный элемент выходит на следующий уровень с "удвоенной мощностью". Надо доработать :)
8 8 2 2 2
8 8 2 2 2 2[/QUOTE]Есть такое, надо учитывать чётность количества элементов. Остаточный, необработанный элемент выходит на следующий уровень с "удвоенной мощностью". Надо доработать :)
Цитата:
Так какое же правильное решение?
Ну не надо говорить! Rebbit, скажи только его сложность :)
Цитата: Der Meister
скажи только его сложность :)
Я лутше о твоей сложности скажу.
С одной стороны ти убираеш елементы с масива. Ето уже бет по сложности. Просто мы етого не видем. Можно сказать что мы будем использовать не масив а связный список. Хорошо. Но как тогда к нему быстро обращаться по индексу ?
Хотя тоже можно, но придется делать спецыфическую структуру данных, которая будет требовать переиндексацыи. :)
ЗЫ. Если чуток поменять реализацыю и не обращаться к елементам по индексам, то можно розрулить ету проблему.
Конечно же, за время меньшее, чем N, задачу решить нельзя.
Самое первое решение, которое напрашивается - это сортровка, а сл-но время N log(N).
Но можно подумать вот над чем.
Доминирующее элемент - это каждый второй елемент, т.к. встречается он в полее половине ячеек. Если эту "вторую" ячейку занял недоминирующий элемент, значит, где-то будут идти два доминирующих элемента подрят.
Думаю, можно как-то развить далее в этом направлении.
Самое первое решение, которое напрашивается - это сортровка, а сл-но время N log(N).
Но можно подумать вот над чем.
Доминирующее элемент - это каждый второй елемент, т.к. встречается он в полее половине ячеек. Если эту "вторую" ячейку занял недоминирующий элемент, значит, где-то будут идти два доминирующих элемента подрят.
Думаю, можно как-то развить далее в этом направлении.
Да вот развиваем уже потихонечку
Цитата: Green
это каждый второй елемент
Я бы даже сказал - каждый нечетный
Цитата: Phodopus
Я бы даже сказал - каждый нечетный
тут без разницы, четный он или нет (ИМХО)
Цитата: t-34
тут без разницы, четный он или нет (ИМХО)
просто в "худшем" (по разумению моего алгоритма) случае - когда число эл-тов нечетное, а число доминант всего на 1 больше числа остальных эл-тов получится массив вида 1,2,1,2,1,2,1,2,1,2,1. Вот я про эти нечетные и говорю.
Цитата:
Я бы даже сказал - каждый нечетный
Не вижу разницы. Скажем, на массиве вида aaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccaaabbcba доминирующий элемент - чётный в первом вхождении. :)
Цитата: Green
Если эту "вторую" ячейку занял недоминирующий элемент, значит, где-то будут идти два доминирующих элемента подрят.
Как уже заметил Phodopus - не всегда. Да и что нам ето даст ? Недоминирующие тоже могут идти подряд.
Даст то, что количество таких "соседств" для доминирующего элемента в любом случае больше, чем для остальных.
Цитата: Der Meister
Даст то, что количество таких "соседств" для доминирующего элемента в любом случае больше, чем для остальных.
Вот-вот-вот.. Кроме единственного случая который я и привел, где "соседств" нет. И не то что бы количество соседств - но их общая значимость. Тоесть когда aabbbbbbaaabbbbbbbaa - "соседств" для "a"-то больше чем для доминирующего "b".
А не заводит ли это решение в строну? И будет ли при реализации это действительно оптимальным алгоритмом?
Цитата: Phodopus
Вот-вот-вот.. Кроме единственного случая который я и привел, где "соседств" нет. И не то что бы количество соседств - но их общая значимость. Тоесть когда aabbbbbbaaabbbbbbbaa - "соседств" для "a"-то больше чем для доминирующего "b".
Верно. Это уже реализовано, но я ищу пары в цикле, а надо рекурсией. Останется та самая первая/последняя "единичка".
Ну, и заменить RemoveAt на вычисление индексов сравниваемых элементов.
Если кто-то уже пробовал, можете выложить хотя бы примерную реализацию этого алгоритма с "соседями"?
Цитата: nikitozz
Если кто-то уже пробовал, можете выложить хотя бы примерную реализацию этого алгоритма с "соседями"?
Мой код и отражает суть.
Неправильно здесь:
Код:
while (list.Count > 1)
ProcessItemPairs(list);
ProcessItemPairs(list);
Цитата: Der Meister
Верно. Это уже реализовано, но я ищу пары в цикле, а надо рекурсией. Останется та самая первая/последняя "единичка".
Ну, и заменить RemoveAt на вычисление индексов сравниваемых элементов.
Ну, и заменить RemoveAt на вычисление индексов сравниваемых элементов.
Как только я первый раз прочитал эту тему - "бросился" решать рекурсией. Потом для себя решил что это доп. память, а значит, читерство :). Шучу на самом деле, но все-таки от рекурсии решил отказаться (да и алгоритм придумал неверный). В итоге сделал итеративно. Алгоритм послал Rebbit через ЛС, но он сказал что его решение куда проще. А выкладывать мой алгоритм сюда или нет - пусть он решает - считаю надо чтоб все-таки интрига оставалась :), но если хотите - пожалуйста (тем более я не уверен насчет его абсолютной корректности).
[QUOTE=nikitozz]И будет ли при реализации это действительно оптимальным алгоритмом?[/QUOTE]Необязательно сравнивать соседей. Можно задать любое правило, выбирающее пары, главное чтобы оно было воспроизводимо (например, идти с концов к центру) и пары не пересекались. Плюс: алгоритм можно заточить под определённую ситуацию. Например, 1, 2, 1, 2, 1, 2, 1 решается за один проход, то есть за N/2 итераций.
Цитата восьмого сообщения, чтобы не сказали, что реализую чужую идею :)
Насколько я понимаю - от N до N*(1 + N/2).
Тестируйте :)
Цитата: Kogrom
А вообще... Смутно представляется алгоритм в котором сравниваем все числа с соседним, а последнее с первым. Если нет равенства, то убираем число из массива, из следующей итерации сравнений. В каждой итерации смотрим были ли убраны числа. Когда перестанут убираться - останутся только доминирующие...
Реализация:
Код:
int testArray(int *a, int sz)
{
vector<int> p(sz), pa(a, a + sz);
while(true)
{
int m = 0;
for(int i = 0; i < sz; ++i)
{
int j = i + 1;
if (j >= sz) j = 0;
if(pa == pa[j])
{
p[m] = pa;
++m;
}
}
if(sz == m) break;
sz = m;
pa = p;
}
int result = p[0];
return result;
}
int main()
{
int mass[11] = {1,1,1,1,1,1,2,2,2,2,2};
cout << testArray(mass, 11) << endl;
return 0;
}
{
vector<int> p(sz), pa(a, a + sz);
while(true)
{
int m = 0;
for(int i = 0; i < sz; ++i)
{
int j = i + 1;
if (j >= sz) j = 0;
if(pa == pa[j])
{
p[m] = pa;
++m;
}
}
if(sz == m) break;
sz = m;
pa = p;
}
int result = p[0];
return result;
}
int main()
{
int mass[11] = {1,1,1,1,1,1,2,2,2,2,2};
cout << testArray(mass, 11) << endl;
return 0;
}
Насколько я понимаю - от N до N*(1 + N/2).
Тестируйте :)
2Rebbit, не подскажите, в правильном ли направлении движение? Или все таки оптимальное решение, которое вы предлагаете в другом направлении? :)
Прошу прощения. На роботе не могу предилить достаточно времени теме. Сравнение парами - ето в сторону того решения которое мне росказали. Его сложность N. (там нет худшего и лутшего случаев)
2Phodopus выкладывай сюда если хочеш.
2Phodopus выкладывай сюда если хочеш.
Код:
TSeq = record
el: Integer;
cnt: Integer;
end;
var
Sq: array [0..1] of TSeq;
P: PIntegerArray;
h, i, j, k, Count, SqIdx, MinElDom, DomEl, T: Integer;
begin
Sq[0].el := P[0];
Sq[0].cnt := 1;
Sq[1].el := 0;
Sq[1].cnt := 0;
SqIdx := 0;
for i := 1 to Count - 1 do
if P <> Sq[SqIdx].el then
begin { переход }
if Sq[1 - SqIdx].el = P then
begin
SqIdx := 1 - SqIdx;
Inc(Sq[SqIdx].cnt);
end
else begin
if Sq[0].cnt > Sq[1].cnt then
SqIdx := 1 { затираем где меньше послед. эл-тов насчиталось }
else
if Sq[0].cnt < Sq[1].cnt then
SqIdx := 0 { затираем где меньше послед. эл-тов насчиталось }
else
SqIdx := 1 - SqIdx; { затираем не последнюю использованную }
Sq[SqIdx].el := P;
Sq[SqIdx].cnt := 1;
end;
end
else
Inc(Sq[SqIdx].cnt);
if Sq[0].cnt > Sq[1].cnt then
ShowMessage(Format('el:%d', [Sq[0].el]))
else
if Sq[0].cnt < Sq[1].cnt then
ShowMessage(Format('el:%d', [Sq[1].el]))
else
ShowMessage(Format('el:%d', [P[0].el]))
el: Integer;
cnt: Integer;
end;
var
Sq: array [0..1] of TSeq;
P: PIntegerArray;
h, i, j, k, Count, SqIdx, MinElDom, DomEl, T: Integer;
begin
Sq[0].el := P[0];
Sq[0].cnt := 1;
Sq[1].el := 0;
Sq[1].cnt := 0;
SqIdx := 0;
for i := 1 to Count - 1 do
if P <> Sq[SqIdx].el then
begin { переход }
if Sq[1 - SqIdx].el = P then
begin
SqIdx := 1 - SqIdx;
Inc(Sq[SqIdx].cnt);
end
else begin
if Sq[0].cnt > Sq[1].cnt then
SqIdx := 1 { затираем где меньше послед. эл-тов насчиталось }
else
if Sq[0].cnt < Sq[1].cnt then
SqIdx := 0 { затираем где меньше послед. эл-тов насчиталось }
else
SqIdx := 1 - SqIdx; { затираем не последнюю использованную }
Sq[SqIdx].el := P;
Sq[SqIdx].cnt := 1;
end;
end
else
Inc(Sq[SqIdx].cnt);
if Sq[0].cnt > Sq[1].cnt then
ShowMessage(Format('el:%d', [Sq[0].el]))
else
if Sq[0].cnt < Sq[1].cnt then
ShowMessage(Format('el:%d', [Sq[1].el]))
else
ShowMessage(Format('el:%d', [P[0].el]))
вот что породил мой воспаленный мосх :). Посмотрите, может есть тест-кейс на котором он и обломается? А то доказывать верность алгоритма не мой конек..
ПыСы. Естественно для массивов с 3 и более элементами
Цитата: Phodopus
Посмотрите, может есть тест-кейс на котором он и обломается? А то доказывать верность алгоритма не мой конек..
ПыСы. Естественно для массивов с 3 и более элементами
ПыСы. Естественно для массивов с 3 и более элементами
Алгоритм почти понравился. Компилятора Паскаля нет, на си++ переводить лень :)
2222111102220
Если правильно понял алгоритм, то первый и последний ноль затрет двойку и результат будет 1.
Цитата: Kogrom
Если правильно понял алгоритм, то первый и последний ноль затрет двойку и результат будет 1.
Мда :). Вечером попробую выкидывать последовательность только если новая найденная - длинее. Была и такая мысль.
Код:
Sq0el := P[0];
Sq0cnt := 1;
Sq1el := 0;
Sq1cnt := 0;
SqIdx := 0;
i := 1;
while (P = Sq0el) and (i < Count) do
begin
Inc(i);
Inc(Sq0cnt);
end;
if i < Count then
begin
Sq1el := P;
Sq1cnt := 0;
for i := i to Count - 1 do
if P <> Sq1el then
begin
if Sq1cnt > Sq0cnt then
begin
Sq0el := Sq1el;
Sq0cnt := Sq1cnt;
end;
Sq1el := P;
Sq1cnt := 1;
end
else
Inc(Sq1cnt);
end;
ShowMessage(Format('el:%d', [Sq0el]));
Sq0cnt := 1;
Sq1el := 0;
Sq1cnt := 0;
SqIdx := 0;
i := 1;
while (P = Sq0el) and (i < Count) do
begin
Inc(i);
Inc(Sq0cnt);
end;
if i < Count then
begin
Sq1el := P;
Sq1cnt := 0;
for i := i to Count - 1 do
if P <> Sq1el then
begin
if Sq1cnt > Sq0cnt then
begin
Sq0el := Sq1el;
Sq0cnt := Sq1cnt;
end;
Sq1el := P;
Sq1cnt := 1;
end
else
Inc(Sq1cnt);
end;
ShowMessage(Format('el:%d', [Sq0el]));
Как-то так, но счаз уже мосх не работает, поэтому могут быть бааааальшие элементарные ляпы..
:mad: чушь написал. На первом же тест-кейсе к предыдущему алгоритму свалился. Но все-равно оставлю здесь.
В воздухе витают хорошые мысли :) Сравнивать парами, выбрасывать из масива. Вопрос в том что выбрасывать и как.