---исходный массив---
aabbbbbbaaabbbbbbbaa
---поехали---
aabbbbbbaaabbbbbbbaa
abbbbbaaabbbbbbbaa
bbbbaaabbbbbbbaa
bbbaabbbbbbbaa
bbabbbbbbbaa
bbbbbbbbaa
bbbbbbba
---ответ---
bbbbbb
Найти доминирующий елемент в масиве (алгоритм)
Задачу задали моему другу на собеседовании в одной более чем извесной фирме. Ответ он дал не самый оптимальный, а я так вообще облажался. Так что и задачу и ответ мне розказали. Думаю вам может быть интересно.
Есть одномерный масив. Извесно что в нем есть доминирующий елемент (тоесть елемент который встречается больше чем в половине ячеек масива). Нужно его найти за минимальную сложность.
Пример: Масив - 1 2 2 2 3 2 Ответ - 2 (потому что 2 встеречаеется более 3-х раз).
Есть одномерный масив. Извесно что в нем есть доминирующий елемент (тоесть елемент который встречается больше чем в половине ячеек масива). Нужно его найти за минимальную сложность.
Пример: Масив - 1 2 2 2 3 2 Ответ - 2 (потому что 2 встеречаеется более 3-х раз).
У меня нарисовалась такая картинка.
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба. После удаления сравнивать начиная с первого. В результате получается массив хотя бы из одного элемента, который и является доминирующим.
Единственное, что смущает, так это сложность. Не оценивал.:)
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба. После удаления сравнивать начиная с первого. В результате получается массив хотя бы из одного элемента, который и является доминирующим.
Код:
Единственное, что смущает, так это сложность. Не оценивал.:)
Порядкова статистика это. Статистика это случаайная велечена. Порядкова потому, что отсортирована в порядке возростания. Примеры порядковых статистик наименьшее число(1 порядковая статистика), наибольшее(N ная), медиана((N+1)/2 для нечетных и N/2 для четных). Так вот алгоритм похож на быструю сортировку. Сложность алгоритма быстрой сортировки N Log N Но нам не нужно пересортировывать весь массив если у нас есть числа которые заведомо больше или заведомо меньши искомого числа то их сортировать не нужно.
Так вот разработан алгоритм для поиска i порядковой статистики. Оценка его в
наихудщем случии N.
Алгоритм сейчас попробую написать. И распишу что к чему.
Так вот разработан алгоритм для поиска i порядковой статистики. Оценка его в
наихудщем случии N.
Алгоритм сейчас попробую написать. И распишу что к чему.
Цитата: Sanila_san
У меня нарисовалась такая картинка.
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба. После удаления сравнивать начиная с первого. В результате получается массив хотя бы из одного элемента, который и является доминирующим.
Единственное, что смущает, так это сложность. Не оценивал.:)
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба. После удаления сравнивать начиная с первого. В результате получается массив хотя бы из одного элемента, который и является доминирующим.
Код:
---исходный массив---
aabbbbbbaaabbbbbbbaa
---поехали---
aabbbbbbaaabbbbbbbaa
abbbbbaaabbbbbbbaa
bbbbaaabbbbbbbaa
bbbaabbbbbbbaa
bbabbbbbbbaa
bbbbbbbbaa
bbbbbbba
---ответ---
bbbbbb
aabbbbbbaaabbbbbbbaa
---поехали---
aabbbbbbaaabbbbbbbaa
abbbbbaaabbbbbbbaa
bbbbaaabbbbbbbaa
bbbaabbbbbbbaa
bbabbbbbbbaa
bbbbbbbbaa
bbbbbbba
---ответ---
bbbbbb
Единственное, что смущает, так это сложность. Не оценивал.:)
Красивое решение! Сложность равна N.
Только после удаления стоит начинать сравнивать не с первого, а с левого от места удаления элемента (если такого нет, то с первого).
[QUOTE="GreenRiver"]Только после удаления стоит начинать сравнивать не с первого, а с левого от места удаления элемента (если такого нет, то с первого).[/QUOTE]Я тоже так подумал, но начинать всегда с первого элемента мне показалось более простым для решения в три часа ночи.:) Потому и сложность не оценивал.
P.S. Решено при помощи анализа на бумаге и курсора в аське, ни единой строки кода не писал.:) На бумаге обнаружилось, что совпадения вида ab не делают погоды, а в аське - уж не помню, как я к этому пришёл - проявился работающий алгоритм, ну и там же проделал десяток тестовых прогонов на разных случаях.
P.S. Решено при помощи анализа на бумаге и курсора в аське, ни единой строки кода не писал.:) На бумаге обнаружилось, что совпадения вида ab не делают погоды, а в аське - уж не помню, как я к этому пришёл - проявился работающий алгоритм, ну и там же проделал десяток тестовых прогонов на разных случаях.
Алгоритм работает (вроде бы всегда), но сложность его N - в лучшем случае, а в худшем, наверное, N log(N).
Но могу и ошибаться.
Но могу и ошибаться.
Цитата: Sanila_san
У меня нарисовалась такая картинка.
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба.
Сравнивать попарно элементы массива, начиная с первого, если они не равны друг другу, то удалять оба.
То есть главная идея вот в чем: если из этого массива удалить два неодинаковых элемента, то в полученном массиве доминирующий элемент останется доминирующим.
Далее я бы сделал по другому. Но это уже технические подробности :)
Код:
int testArray(int *a, int sz)
{
vector<int> p(sz), pa(a, a + sz);
int m = 0;
while(sz)
{
m = 0;
int i;
for(i = 0; i < sz; i += 2)
{
if(pa == pa[i + 1])
{
p[m] = pa;
++m;
}
}
if(!m) p[0] = pa.back(); // если нечетное количество элементов
if(m <= 3) break;
sz = m;
pa = p;
}
if(m == 3) // если нечетное количество элементов
if(p[0] != p[2])
p[0] = p[1];
p[0];
return p[0];
}
int main()
{
const int sz = 13;
int mass[sz] = {2,2,2,2,2,2,1,1,1,1,1,1,2};
cout << testArray(mass, sz) << endl;
return 0;
}
{
vector<int> p(sz), pa(a, a + sz);
int m = 0;
while(sz)
{
m = 0;
int i;
for(i = 0; i < sz; i += 2)
{
if(pa == pa[i + 1])
{
p[m] = pa;
++m;
}
}
if(!m) p[0] = pa.back(); // если нечетное количество элементов
if(m <= 3) break;
sz = m;
pa = p;
}
if(m == 3) // если нечетное количество элементов
if(p[0] != p[2])
p[0] = p[1];
p[0];
return p[0];
}
int main()
{
const int sz = 13;
int mass[sz] = {2,2,2,2,2,2,1,1,1,1,1,1,2};
cout << testArray(mass, sz) << endl;
return 0;
}
Мой вроде тоже заработал
Это тот же вариант, что и мой первый, но вроде рабочий и без списков. На скорую руку набросанный тест
вроде проходит
Код:
// Интерфейсный метод
public static T GetDominant<T>(T[] source)
{
T[] items = (T[]) source.Clone();
if (ProcessPairs(items, items.Length) == 0)
throw new Exception("No dominant");
return items[0];
}
// Рабочий метод
static int ProcessPairs<T>(T[] items, int count)
{
while (count > 1)
{
int newcount = 0;
for (int i = 0; i < count - 1; i += 2)
{
T left = items;
T right = items[i + 1];
if (left.Equals(right)) // same as left == right
{
items[newcount] = left;
newcount++;
}
}
if (count % 2 != 0 && newcount % 2 == 0)
{
items[newcount] = items[count - 1];
newcount++;
}
count = newcount;
}
return count;
}
public static T GetDominant<T>(T[] source)
{
T[] items = (T[]) source.Clone();
if (ProcessPairs(items, items.Length) == 0)
throw new Exception("No dominant");
return items[0];
}
// Рабочий метод
static int ProcessPairs<T>(T[] items, int count)
{
while (count > 1)
{
int newcount = 0;
for (int i = 0; i < count - 1; i += 2)
{
T left = items;
T right = items[i + 1];
if (left.Equals(right)) // same as left == right
{
items[newcount] = left;
newcount++;
}
}
if (count % 2 != 0 && newcount % 2 == 0)
{
items[newcount] = items[count - 1];
newcount++;
}
count = newcount;
}
return count;
}
Код:
static void RandomTest()
{
Random rnd = new Random(Environment.TickCount);
for (int testid = 0; testid < 100000; testid++)
{
int count = rnd.Next(200) + 2; // Общее количество элементов
// Разность между общим количеством элементов
// и количеством вхождений доминирующего элемента
int difference = rnd.Next(count / 2 - 1);
// Количество вхождений доминирующего элемента
int dominantcount = count - difference;
// Сам доминирующий элемент
int dominant = rnd.Next(20);
List<int> positions = new List<int>();
for (int i = 0; i < count; i++)
positions.Add(i);
int[] source = new int[count];
// Размещаем доминирующий элемент случайным образом dominantcount раз
for (int i = 0; i < dominantcount; i++)
{
int index = rnd.Next(positions.Count);
int position = positions[index];
source[position] = dominant;
positions.RemoveAt(index);
}
// В остальные позиции кладём случайные элементы
foreach (int position in positions)
source[position] = rnd.Next(20);
// Тестируем
int d = GetDominant(source);
if (d != dominant)
{
string message = "{ ";
foreach (int n in source)
message += n.ToString() + " ";
message += "}\n";
message += string.Format("expected {0} got {1}", dominant, d);
Console.WriteLine(message);
}
}
}
{
Random rnd = new Random(Environment.TickCount);
for (int testid = 0; testid < 100000; testid++)
{
int count = rnd.Next(200) + 2; // Общее количество элементов
// Разность между общим количеством элементов
// и количеством вхождений доминирующего элемента
int difference = rnd.Next(count / 2 - 1);
// Количество вхождений доминирующего элемента
int dominantcount = count - difference;
// Сам доминирующий элемент
int dominant = rnd.Next(20);
List<int> positions = new List<int>();
for (int i = 0; i < count; i++)
positions.Add(i);
int[] source = new int[count];
// Размещаем доминирующий элемент случайным образом dominantcount раз
for (int i = 0; i < dominantcount; i++)
{
int index = rnd.Next(positions.Count);
int position = positions[index];
source[position] = dominant;
positions.RemoveAt(index);
}
// В остальные позиции кладём случайные элементы
foreach (int position in positions)
source[position] = rnd.Next(20);
// Тестируем
int d = GetDominant(source);
if (d != dominant)
{
string message = "{ ";
foreach (int n in source)
message += n.ToString() + " ";
message += "}\n";
message += string.Format("expected {0} got {1}", dominant, d);
Console.WriteLine(message);
}
}
}
Kogrom
:)
Проверь для 2 2 2 2 8 8 8 8 2 и 2 2 2 2 2 8 8 8 8
:)
Проверь для 2 2 2 2 8 8 8 8 2 и 2 2 2 2 2 8 8 8 8
Цитата: Der Meister
Kogrom
:)
Проверь для 2 2 2 2 8 8 8 8 2 и 2 2 2 2 2 8 8 8 8
:)
Проверь для 2 2 2 2 8 8 8 8 2 и 2 2 2 2 2 8 8 8 8
И? У меня двойку выдает (по крайней мере в программе предпоследнего моего сообщения).
Просьба: писать массив через запяятые: лень их вставлять :)
Цитата: Green
Алгоритм работает (вроде бы всегда), но сложность его N - в лучшем случае, а в худшем, наверное, N log(N).
Но могу и ошибаться.
Но могу и ошибаться.
Я даже рискну сказать, что сложность меньше N, в зависимости от содержимого.
Конечно при условии, что начинаем не с первого, а с "левого".
Я прогнал (в уме :)) крайние варианты: одинаковые элементы подряд (ааааа), разные элементы подряд (ababa)
Код:
---исходный массив---
aaaaа
---сравнения---
aaaaа
ааааа
ааааа
ааааа
---результат---
4
aaaaа
---сравнения---
aaaaа
ааааа
ааааа
ааааа
---результат---
4
Код:
---исходный массив---
ababа
---сравнения---
ababа
aba
a
---результат---
2
ababа
---сравнения---
ababа
aba
a
---результат---
2
Цитата:
лень их вставлять
Аналогично
Цитата:
И? У меня двойку выдает (по крайней мере в программе предпоследнего моего сообщения).
Тогда всё тип-топ, поздравляю :)
Предлагаю подумать над оптимальным алгоритмом проверки предусловия: есть ли в массиве длиной N некоторый элемент, встречающийся более N / 2 раз? Что тут можно придумать (помимо сортировки, опять же)?
Цитата: GreenRiver
Я даже рискну сказать, что сложность меньше N, в зависимости от содержимого.
Под сложностью понимаем O-большое?
Тогда сложность меньше N подразумевает, что это делается за время меньше линейно зависящего от кол-ва элементов. А это не так.
Нам необходимо просмотреть ВСЕ ячейки массива, чтоб решить эту задачу, а сл-но сложность не может быть меньше N.
Что касается примеров, то там линейная зависимость, - ровно N обращений к ячейкам массива.
Можно привести примеры, где кол-во это будет больше N, например: aabbaabbaa.
А как насчет того чтобы не удалять, а, к примеру, вести 2 индекса. А то удаление - это или доп. память, или доп. сложность, разве не так?
Что-то вроде: выпускаем 2 указателя на эл-ты массива. Изначально на 1ый и второй эл-т соответственно. Если эл-ты по указателям равны, первый указатель принимает значение второго, а второй переходит к следующему элементу, если не равны - первый откатывается назад (если есть куда) а второй продвигается вперед.. Главное чтобы второй указатель назад по массиву не вернулся в одном из шагов, и первый в случае "удаления" самого левого элемента встал на корректную позицию..
Что-то вроде: выпускаем 2 указателя на эл-ты массива. Изначально на 1ый и второй эл-т соответственно. Если эл-ты по указателям равны, первый указатель принимает значение второго, а второй переходит к следующему элементу, если не равны - первый откатывается назад (если есть куда) а второй продвигается вперед.. Главное чтобы второй указатель назад по массиву не вернулся в одном из шагов, и первый в случае "удаления" самого левого элемента встал на корректную позицию..
[QUOTE=Green]Нам необходимо просмотреть ВСЕ ячейки массива, чтоб решить эту задачу, а сл-но сложность не может быть меньше N.[/QUOTE]У меня количество итераций на каждом уровне как минимум вдвое меньше, чем на предыдущем, а на первом их (N + 1) / 2. В общем это вроде от N до 2*N - 1 (в худшем случае) обращений к источнику последовательности. Rebbit заявляет, что сложность его алгоритма О большое от N в точности. Значит, пары - хорошая, но не лучшая идея?
Мне Rebbit тоже говорил, что там строго линейная сложность. :) В моём алгоритме (в том его виде, как я описал) сложность не строго линейная, поскольку существуют лишние проходы. Собственно, она линейной будет только когда имеется массив abababababa - тогда, если не начинать сначала каждый раз, то сложность линейная. Возможно, следует как-то иначе сравнивать парами. :) Кроме того, как подсказка, Rebbit утвержает, что для того алгоритма сложность не зависит от случая. Я пока не знаю, как это сделать.
Цитата: Sanila_san
Кроме того, как подсказка, Rebbit утвержает, что для того алгоритма сложность не зависит от случая. Я пока не знаю, как это сделать.
Вот розпросят по аське, а потом продадут.
Короче все правильно. Выбрасывать парами надо и тогда ответ останется невыброшеным. По сути задачу решыли, осталось только написать хорошую реализацыю, но ето уже дело техники. А один проход или несколько - неважно. Главное O(N)
Цитата: Sanila_san
Мне Rebbit тоже говорил, что там строго линейная сложность. :) В моём алгоритме (в том его виде, как я описал) сложность не строго линейная, поскольку существуют лишние проходы. Собственно, она линейной будет только когда имеется массив abababababa - тогда, если не начинать сначала каждый раз, то сложность линейная. Возможно, следует как-то иначе сравнивать парами. :) Кроме того, как подсказка, Rebbit утвержает, что для того алгоритма сложность не зависит от случая. Я пока не знаю, как это сделать.
В любом случае, при проверке парами результат непредсказуем, если в массиве нет элемента, поподающего под определение "доминирующий". Я вот всё надеюсь, что есть метод, позволяющий и проверку предусловия заодно проводить.
Цитата: Rebbit
По сути задачу решыли
Уфф.
Это значит, что коллективный разум участников форума смог бы работать в "одной более чем извесной фирме", если бы думал в десятки раз быстрее :)
Цитата: Phodopus
А как насчет того чтобы не удалять, а, к примеру, вести 2 индекса. А то удаление - это или доп. память, или доп. сложность, разве не так?
Что-то вроде: выпускаем 2 указателя на эл-ты массива. Изначально на 1ый и второй эл-т соответственно. Если эл-ты по указателям равны, первый указатель принимает значение второго, а второй переходит к следующему элементу, если не равны - первый откатывается назад (если есть куда) а второй продвигается вперед.. Главное чтобы второй указатель назад по массиву не вернулся в одном из шагов, и первый в случае "удаления" самого левого элемента встал на корректную позицию..
Что-то вроде: выпускаем 2 указателя на эл-ты массива. Изначально на 1ый и второй эл-т соответственно. Если эл-ты по указателям равны, первый указатель принимает значение второго, а второй переходит к следующему элементу, если не равны - первый откатывается назад (если есть куда) а второй продвигается вперед.. Главное чтобы второй указатель назад по массиву не вернулся в одном из шагов, и первый в случае "удаления" самого левого элемента встал на корректную позицию..
Красота :)
Код:
int testArray(int *a, int sz)
{
int *p1 = a, *p2 = a + 1;
while(p2 < a + sz - 1)
{
if(*p1 == *p2)
{
p1++;
}
else
{
if(p1 - a > 0)p1--;
}
p2++;
}
return *p1;
}
int main()
{
const int sz = 9;
//int mass[sz] = {2, 2, 2, 2, 2, 8, 8, 8, 8};
int mass[sz] = {2, 8, 2, 8, 2, 8, 2, 8, 2};
cout << testArray(mass, sz) << endl;
return 0;
}
{
int *p1 = a, *p2 = a + 1;
while(p2 < a + sz - 1)
{
if(*p1 == *p2)
{
p1++;
}
else
{
if(p1 - a > 0)p1--;
}
p2++;
}
return *p1;
}
int main()
{
const int sz = 9;
//int mass[sz] = {2, 2, 2, 2, 2, 8, 8, 8, 8};
int mass[sz] = {2, 8, 2, 8, 2, 8, 2, 8, 2};
cout << testArray(mass, sz) << endl;
return 0;
}
Правда, особо не тестировал.
Цитата: Der Meister
В любом случае, при проверке парами результат непредсказуем, если в массиве нет элемента, поподающего под определение "доминирующий". Я вот всё надеюсь, что есть метод, позволяющий и проверку предусловия заодно проводить.
Ну, я-то решал задачу, в которой по условию такой элемент был. Мой алгоритм, кстати, возвращает NULL, если доминирующий элемент не найден. :)
Цитата: Green
Под сложностью понимаем O-большое?
Тогда сложность меньше N подразумевает, что это делается за время меньше линейно зависящего от кол-ва элементов. А это не так.
Нам необходимо просмотреть ВСЕ ячейки массива, чтоб решить эту задачу, а сл-но сложность не может быть меньше N...
Тогда сложность меньше N подразумевает, что это делается за время меньше линейно зависящего от кол-ва элементов. А это не так.
Нам необходимо просмотреть ВСЕ ячейки массива, чтоб решить эту задачу, а сл-но сложность не может быть меньше N...
Сложность алгоритма определяется не количеством обращений к единице массива (это справедливо только для поиска), имхо. При поиске каждый элемент сравнивается с искомым выражением, следовательно основная часть алгоритма будет работать с каждым элементом. В нашем случае основная операция сравнение двух элементов - их я и считал.
Относительно того может ли быть сложность меньше N (для сортировки - нет, но мы ведь и не сортируем ;)).
Правда О большое это абстрагирование от лишних слагаемых: N-1 => O(n). Так что сложность все таки O(N).
P.S. а вообще классная задача :) "известная фирма" была наверное не прочь заполучить коллективный разум :)
Цитата: GreenRiver
"известная фирма" была наверное не прочь заполучить коллективный разум :)
forum.codenet.ru не продается! :D
Цитата: Kogrom
Красота :)
...
Правда, особо не тестировал.
...
Правда, особо не тестировал.
Потестировал идею от Phodopus. Не работает :(
Придется наворачивать что-то типа:
Код:
#include <iostream>
int testArray(int *a, int sz)
{
int *p1 = a, *p2 = a + 1, *p3 = 0;
while(p2 < a + sz - 1)
{
if(*p1 == *p2)
{
p1 = p2;
p3 = p1; // Точка возврата
}
else
{
if(p3 && (p1 != p3))
p1 = p3; // Возвращаемся
else
{
p3 = 0; // Больше некуда возвращаться
p1 += 2;
p2++;
}
}
p2++;
}
return *p1;
}
int main()
{
const int sz = 9;
int mass[sz] = {2, 8, 2, 8, 2, 8, 2, 8, 2};
std::cout << testArray(mass, sz) << std::endl;
return 0;
}
int testArray(int *a, int sz)
{
int *p1 = a, *p2 = a + 1, *p3 = 0;
while(p2 < a + sz - 1)
{
if(*p1 == *p2)
{
p1 = p2;
p3 = p1; // Точка возврата
}
else
{
if(p3 && (p1 != p3))
p1 = p3; // Возвращаемся
else
{
p3 = 0; // Больше некуда возвращаться
p1 += 2;
p2++;
}
}
p2++;
}
return *p1;
}
int main()
{
const int sz = 9;
int mass[sz] = {2, 8, 2, 8, 2, 8, 2, 8, 2};
std::cout << testArray(mass, sz) << std::endl;
return 0;
}
Цитата: Phodopus
forum.codenet.ru не продается! :D
- Наивные... - пробормотал, воровато озираясь, mike, и скрылся во мгле ночного переулка. В его руке был чемоданчик, набитый новенькими хрустящими купюрками :D
Код:
// string Text = aaaaaaabbbbbbbbbbbbbbbcccccccccc
// bool Ascending = sort dictionary
private Dictionary<char, int> CalcChars(string Text, bool Ascending)
{
// Creating a Dictionary
Dictionary<char, int> charsDic = new Dictionary<char, int>();
int i = 0;
CharEnumerator charEnum = Text.GetEnumerator();
while (charEnum.MoveNext())
{
char ch = Text;
if (charsDic.ContainsKey(ch))
{
charsDic[ch]++;
}
else
{
charsDic.Add(ch, 0);
}
i++;
}
// Sorting a Dictionary
List<KeyValuePair<char, int>> rList = new List<KeyValuePair<char, int>>(charsDic);
if (Ascending)
{
rList.Sort(delegate(KeyValuePair<char, int> first, KeyValuePair<char, int> second)
{
return first.Value.CompareTo(second.Value);
}
);
}
else
{
rList.Sort(delegate(KeyValuePair<char, int> first, KeyValuePair<char, int> second)
{
return second.Value.CompareTo(first.Value);
}
);
}
// Clear Dictionary
charsDic.Clear();
foreach (KeyValuePair<char, int> np in rList)
{
charsDic.Add(np.Key, np.Value);
}
return charsDic;
}
// bool Ascending = sort dictionary
private Dictionary<char, int> CalcChars(string Text, bool Ascending)
{
// Creating a Dictionary
Dictionary<char, int> charsDic = new Dictionary<char, int>();
int i = 0;
CharEnumerator charEnum = Text.GetEnumerator();
while (charEnum.MoveNext())
{
char ch = Text;
if (charsDic.ContainsKey(ch))
{
charsDic[ch]++;
}
else
{
charsDic.Add(ch, 0);
}
i++;
}
// Sorting a Dictionary
List<KeyValuePair<char, int>> rList = new List<KeyValuePair<char, int>>(charsDic);
if (Ascending)
{
rList.Sort(delegate(KeyValuePair<char, int> first, KeyValuePair<char, int> second)
{
return first.Value.CompareTo(second.Value);
}
);
}
else
{
rList.Sort(delegate(KeyValuePair<char, int> first, KeyValuePair<char, int> second)
{
return second.Value.CompareTo(first.Value);
}
);
}
// Clear Dictionary
charsDic.Clear();
foreach (KeyValuePair<char, int> np in rList)
{
charsDic.Add(np.Key, np.Value);
}
return charsDic;
}
Цитата: akasex
Код:
дофиг кода
Идея понятна, но чет слишком многословно. Вот кратко и обобщенно (да и без ненужной сортировки):
Код:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1 {
class Program {
public static bool TryFindDominator<T>(T[] array, out T dominator) {
int bound_value = (array.Length / 2);
int current_dominator_count = 0;
T current_dominator = default(T);
Dictionary<T, int> item_count_table = new Dictionary<T, int>(array.Length);
foreach (T item in array) {
int count_value;
if (item_count_table.TryGetValue(item, out count_value)) {
count_value += 1;
} else {
count_value = 1;
}
item_count_table[item] = count_value;
if (count_value > current_dominator_count) {
current_dominator_count = count_value;
current_dominator = item;
if (current_dominator_count > bound_value)
break;
}
}
dominator = current_dominator;
return (current_dominator_count > bound_value);
}
static void Main(string[] args) {
int[] test = new int[] { 1, 2, 3, 3, 3, 3, 3, 5 };
int possible_dominator;
bool dominator_found = TryFindDominator<int>(test, out possible_dominator);
Console.WriteLine("Found: {0}", dominator_found);
Console.WriteLine("Possible dominator: {0}", possible_dominator);
Console.ReadLine();
}
}
}
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1 {
class Program {
public static bool TryFindDominator<T>(T[] array, out T dominator) {
int bound_value = (array.Length / 2);
int current_dominator_count = 0;
T current_dominator = default(T);
Dictionary<T, int> item_count_table = new Dictionary<T, int>(array.Length);
foreach (T item in array) {
int count_value;
if (item_count_table.TryGetValue(item, out count_value)) {
count_value += 1;
} else {
count_value = 1;
}
item_count_table[item] = count_value;
if (count_value > current_dominator_count) {
current_dominator_count = count_value;
current_dominator = item;
if (current_dominator_count > bound_value)
break;
}
}
dominator = current_dominator;
return (current_dominator_count > bound_value);
}
static void Main(string[] args) {
int[] test = new int[] { 1, 2, 3, 3, 3, 3, 3, 5 };
int possible_dominator;
bool dominator_found = TryFindDominator<int>(test, out possible_dominator);
Console.WriteLine("Found: {0}", dominator_found);
Console.WriteLine("Possible dominator: {0}", possible_dominator);
Console.ReadLine();
}
}
}
UPD: добавил прерывание цикла при нахождении доминирующего элемента (больше половины длины массива). Т.о. сложность алгоритма: от O(N /2) в лучшем случае до O(N), где N - длина массива.