Какое число не содержится в массиве

Задача: в массиве длиной 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