Комментарии 14
Сразу приходят на ум распределённые базы данных с правилом успешной записи в N/2+1 реплику. Применяют там такой алгоритм?
Если допустить, что кандидаты нумеруются с единицы и последовательно (либо нам заранее известен максимальный номер ну или если у нас есть неограниченное количество памяти), то можно в общем и в один проход, используя гистограмму, ну вот как-то так что ли:
public static int findMajority(int[] nums)
{
int count = 0, candidate = -1;
int[] histo = new int[nums.Length + 1]; //Assumed sequential order
// Finding majority candidate
for (int index = 0; index < nums.Length; index++) {
if (histo[nums[index]]++ > count) {
count = histo[nums[index]];
candidate = nums[index];
}
}
if (count > (nums.Length / 2)) return candidate; else return -1;
}
Тут пространственная сложность становится O(N) на выделение собственно гисты. Теоретически можно пожать исходный массив при помощи RLE, но тут все равно крайние случаи возникают.
Сортировка имеет сложность больше чем O(1)
алгоритм работает и на неотсортированном массиве. К сожалению, выбор данных для иллюстрации неудачный — глаз сразу подмечает сортировку, хотя она не влияет на результат работы.
На самом деле при проходе ищется преобладающий элемент в некоем (возможно, уменьшающемся) подмассиве данных, отбрасывая подмассивы без преобладающего элемента, а потом проверяется, что этот элемент преобладает во всем массиве. За счет того, что проверяется N/2+1 сбить в 0 этот элемент не получится во всех случаях, все равно он вылезет в конце первого прохода, как его не прячь за другими (второстепенными) элементами. Второй проход для проверки ложноположительного результата.
Теория принятия решений подъехала, любо.
Классика )
Прикольно, что этот подход можно обобщить на поиск (k-1) элементов, каждый из которых встречается более 1/k раз. Например, если k=3, то вместо аннигиляции пар элементов аннигилируем тройки.
Еще есть алгоритм, не шибко расширяемый в общем случае, но все равно забавный. Если говорить о числах, можем каждое встреченное число разбивать на биты и суммировать вхождения каждого бита.
В конце за О(log(максимальное число)) проходим по массиву битов и берем только те, которые встречаются больше половины раз.
Очевидно, это не сработает, если нам не гарантировано, что такое число вообще есть (а если гарантированно - то и Бойер-Мур сработает за одну линию). Контртест - банальный
(1,2,3). При подсчете битов получим (0,2,2) - что даст неправильный ответ 3.
Но, подозреваю, что по времени работы эти алгоритмы вполне соизмеримы на больших массивах.
Класно! Очень необычный подход. В таком формате над этой задачей я не думал даже. Не очень понял, почему O(log(n)) для прохождения по массиву битов, но если инты брать, то можно за константу по битам пройтись. Проблема будет наверное только со знаковым битом.
Там, все же, не O(log(n)), а O(log(максимальное число)), потому что в общем случае никто не гарантирует, что числа на входе помещаются в int. Если максимальное число включает в себя 10000 бит - то и этот массив с битами будет 10000 и по нему тоже придется пройтись.
По поводу идеи с интом, можно:
1) Если мы знаем размер массива заранее.
2) Если мы знаем, что существует такой элемент.
3) Если мы знаем битность максимально-возможного числа.
Тогда в ответ вписывать бит как только кол-во его вхождений перевалит за половину. Тогда этот последний обход можно упразднить.
Но, конечно, исходный алгоритм намного проще расширять. Скажем, если там не числа, а строки, или вообще какие-то кастомные классы. Можно, конечно, что-то с хешами выдумывать, конвертировать в void*, писать свои превращения класса в bitfield - но Бойер-Мур явно и понятно, без всяких извращений - работает для любых типов, для которых определены operator= и operator==.
И все равно алгоритм с битами - прикольный.
Тут придется на каждой итерации проходить биты числа. Асимптотика линейная, а работать будет дольше.
Ну и можно такое делать не только на целых, а и на вещественных числах. В некоторых языках (напр., с, с++, js) есть возможность смотреть биты вещественных чисел.
А что, по-вашему, сравнение двух чисел происходит как-то не по-битово? Конечно, компилятор это делает как-то быстрее, сравнивая не по одному биту, а по 32, скажем, или по 64. Собственно, поэтому мы и опускаем этот множитель из асимптотики в алгоритме Бойера-Мура, хотя там есть и сравнения, и присваивания.
Я сразу указал, что асимптотика будет не просто O(n), а, O(n * log(max(num))). Что можно ограничить сверху константой. Иногда. Ну, например 64.
O(64n)=O(n). Для больших массивов чисел эта константа роли не играет, сильно зависит от реализации и все такое.
Для желающих поиграться с оптимизацией, вот запилил на quickbench: https://quick-bench.com/q/AB50Bom9Nn1x9ZXkpTGKGEr_njQ
И, ожидаемо, Бойера-Мура быстрее. В зависимости от данных - вплоть до двух порядков быстрее.
del
Алгоритм большинства голосов Бойера — Мура