Эффективный алгоритм «разделяй и властвуй»

Question

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

Решение грубой силы будет состоять в том, чтобы поддерживать два указателя на массиве участников, представляя n участников для n-1 других участников за время O (n ² ). Я не могу понять, как улучшить это.

Редактировать: Формально,

You are given an integer n. There is a hidden array A of size n, such that more than half of the values in A are the same. This array represents the party affiliation of each person.

You are allowed queries of the form introduce(i, j), where i≠j, and 1 <= i, j <= n, and you will get a boolean value in return: You will get back 1, if A[i] = A[j], and 0 otherwise.

Output: B ⊆ [1, 2. ... n] where |B| > n/2 and the A-value of every element in B is the same.

Надеюсь, это лучше объясняет проблему.

Answer 1

Это может быть сделано в O (n) введениях с использованием алгоритма большинства голосов Бойера-Мура .

Рассмотрим произвольный порядок участников: A_1, A_2, ..., A_n. В алгоритме вы сохраняете «сохраненный элемент», обозначаемый m. Всякий раз, когда алгоритм хочет проверить, совпадает ли текущий элемент (x) с сохраненным элементом, вы вводите этих двух людей и соответственно увеличиваете или уменьшаете счетчик. Сохраненный элемент в конце будет членом партии большинства. Затем вы можете сделать еще один проход для всех остальных n - 1 человек и представить каждого из них этому известному человеку и, следовательно, найти всех членов партии большинства.

Таким образом, общее количество представлений составляет О (п).