Я пытаюсь решить проблему, описанную в моем вопросе: Эффективный алгоритм "разделяй и властвуй"
Для этого расширения, как известно, есть представители от 3 сторон на на мероприятии присутствуют больше участников для одной стороны, чем для любой другой. Формальное описание проблемы можно найти ниже.
Вам дано целое число n. Существует скрытый массив A размера n, который содержит элементы, которые могут принимать 1 из 3 значений. Существует значение, пусть это будет m, которое встречается в массиве чаще, чем другие 2 значения.
Вам разрешены запросы вида вводить (i, j), где i ≠ j и 1 <= i , j <= n, и вы получите взамен логическое значение: вы получите обратно 1, если A [i] = A [j], и 0 в противном случае. <br>Выход: B ⊆ [1, 2.. .. n], где A-значение каждого элемента в B равно m.
Решение этой грубой силы может вычислить B в O (n 2 ), вызвав ввод (i , j) для n (n-1) комбинаций элементов и создания 3 списков, содержащих A-индексы элементов, для которых был возвращен 1, когда для них был вызван ввод, возвращая список наибольшего размера.
Я понимаю Алгоритм голосования Бойера – Мура , но он не может найти способ изменить его для этой проблемы или найти эффективный алгоритм для ее решения.