Поскольку я читал это (Найти наиболее распространенную запись в массиве), Было предложено алгоритм голосового алгоритма Бойера и Мура.
Если вы переходите по ссылке на сайт, есть пошаговое объяснение того, как работает алгоритм. Для данной последовательности AAACCBBCCCBCC
оно представляет правильное решение.
Когда мы перемещаем указатель вперед элемент e:
- Если счетчик равен 0, мы устанавливаем текущий кандидат в e, и мы устанавливаем против 1.
- Если счетчик не равен 0, мы увеличиваем или уменьшаем счетчик в зависимости от того, является ли e текущим кандидат.
Когда мы закончим, текущий кандидат является элементом большинства, если есть большинство.
Если я использую этот алгоритм на листе бумаги с AAACCBB
как входной, , предложенный кандидат станет B, что явно неверно.
Как я вижу, есть две возможности
- Авторы никогда не пробовали свой алгоритм ничем иным, кроме
AAACCBBCCCBCC
, полностью некомпетентны и должны быть уволены на месте (сомнительно). - Мне явно не хватает чего-то, должен быть запрещен из Stackoverflow и никогда больше не должен позволять касаться всего, что связано с логикой.
Примечание. Ниже приведена реализация алгоритма на С++ от Niek Sanders. Я считаю, что он правильно реализовал эту идею и, как таковой, имеет ту же проблему (или не так ли?).