Поиск часто встречающихся элементов в массиве

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.

Реализация алгоритма Бойера-Мура занимает всего несколько строк:

int* majority(int[] array, int N) {   int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять   int* candidate = NULL; // последний человек, не нашедший пару --                           // возможно, его элемент встречается чаще всего    // проходим по массиву и усаживаем пары с разными элементами   for (int i = 0; i<N; i++) {      // если до сих пор все сидят, то следующему пока придётся постоять     if (confidence == 0) {       candidate = array+i;       confidence++;     }      // иначе следующий либо садится с одним из стоящих,     // либо будет стоять вместе с ними, если у него такой же элемент     else if (*candidate == array[i]))        confidence++;     else        confidence--;   }    return confidence > 0 ? candidate : NULL; } 

В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.

Усложним задачу. Теперь в массиве длиной N надо найти элементы, которые повторяются больше N/3 раз — если есть два, то оба, если есть один, то один.

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

Идею прошлого алгоритма несложно обобщить и для троек: пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.

Код мало отличается от предыдущего: по-прежнему один проход по массиву и O(1) дополнительной памяти.

void majority(int[] array, int N, int** cand1, int** cand2) {   int conf1 = 0, conf2 = 0; // количество стоящих людей с двумя элементами   *cand1 = NULL; *cand2 = NULL; // два стоящих человека с разными элементами    // проходим по массиву и усаживаем тройки с разными элементами   for (int i = 0; i<N; i++) {      // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними     if (conf1 > 0 && **cand1 == array[i])       conf1++;     else if (conf2 > 0 && **cand2 == array[i])       conf2++;     else // может, стоят только с одним элементом, или вообще стоящих нет?       if (conf1 == 0) {         *cand1 = array+i;         conf1++;       } else if (conf2 == 0) {         *cand2 = array+i;         conf2++;       }     else { // стоят с двумя другими элементами, так что усаживаем всю тройку       conf1--;       conf2--;     }   }    if(conf1 == 0) *cand1 = NULL;   if(conf2 == 0) *cand2 = NULL; } 

Этот алгоритм опубликован в 1982 американскими учёными Джаядевом Мисрой и Дэвидом Грисом (Jayadev Misra & David Gries), и в их работе используется более скучная метафора — мешок с N числами, из которого они извлекают по 3 разных числа за каждую операцию. Кроме того, их псевдокод не похож ни на один понятный современному программисту язык. Мне больше понравилось объяснение их алгоритма в позапрошлогоднем конспекте лекций американского профессора Амита Чакрабарти.

В наиболее общей форме, когда в массиве длиной N надо найти элементы, которые повторяются больше N/k раз — придётся-таки воспользоваться словарём. Хранить в словаре мы будем только те элементы, с которыми люди стоят — т.е. не больше k-1 записей.

int[] majority(int[] array, int N, int k) {   // словарь стоящих людей изначально пуст   Dictionary<int,uint> candidates = new Dictionary<int,uint>{};    // проходим по массиву и усаживаем группы по k   for (int i = 0; i<N; i++) {      // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними     if (candidates.ContainsKey(array[i]))       candidates[array[i]]++;     else // может, стоят менее чем с k-1 элементами?       if (candidates.Count < k - 1)         candidates[array[i]] = 1;     else // стоят с k-1 другими элементами, так что усаживаем всю группу       foreach(int l in candidates.Keys)         if (candidates[l]-- == 0)              // (**)           candidates.Remove(l);                // (*)   }    return candidates.Keys.ToArray(); } 

В этой наиболее общей форме алгоритма — по-прежнему один проход по массиву и O(k) дополнительной памяти. Если мы пользуемся для реализации словаря хэш-таблицей, а все записи в словаре свяжем в список — тогда общая сложность алгоритма останется линейной: строчка (*) с удалением записи из словаря выполняется самое большее N раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

Таким образом наше устройство с маленькой памятью смогло бы общаться с одним пушистым зверьком, недавно препарированным хабраумельцами. Сигналы этого зверька имеют пять логических уровней: полагаем k=6, и получаем все пять уровней прямо на ходу, даже без сохранения сигнала в память. Нужно только обеспечить протоколом, чтобы все пять уровней встречались в сигнале одинаково часто.

Для алгоритма Мисры-Гриса упоминаются и другие применения. Например, можно следить в реальном времени за трафиком в сети, и если некий один хост потребляет непропорционально большую часть трафика — начинать расследование. Так же можно следить за кликами по баннерам, за финансовыми транзакциями, за потоком инструкций в моделируемом процессоре… В общем, всюду, где большое число повторений — подозрительная аномалия.

За оживление текста иллюстрациями надо благодарить Nitatunarabe