我正在尝试解决对我在问题中描述的问题的扩展：Efficient divide-and-conquer algorithm对于此扩展，已知有3个政党的代表参加该活动，并且1个政党参加的成员人数超过了其他任何政党。有关问题的正式描述，请参见下面。
您得到一个整数n。有一个大小为n的隐藏数组A，其中包含可以采用3个值之一的元素。有一个值，使它为m，在数组中比其他2个值更经常出现。允许您查询形式为Introduction（i，j），其中i≠j，并且1 <= i，j <= n，并且您将获得布尔值作为回报：如果A [i ] = A [j]，否则为0。输出：B⊆[1，2. ... n]，其中B中每个元素的A值为m。
对此的蛮力解决方案可以通过对n（n-1）个元素组合调用Introduction（i，j）并创建3个包含元素A索引的列表来计算O（n 2）中的B当在他们上引入Introduction时返回1，返回最大的列表。我了解Boyer–Moore majority vote algorithm，但找不到解决此问题的方法或找到解决问题的有效算法。
扫描所有A [i] = A [0]，并为所有i列出A [i]！= A [0]的列表I []。然后扫描所有A [I [i]] = A [I [0]]，依此类推。对于A []中的每个可能值，都需要进行一次O（n）扫描。