有效的分治算法

Question

[在政治事件中，介绍2个人确定他们是否代表同一政党。假设n个参与者中有一半以上代表同一方。我正在尝试找到一种有效的算法来识别该方的代表。

一种蛮力解决方案将在与会者阵列上进行两次迭代，在O（n ²）时间内将n位与会者引入n-1个其他与会者。我不知道该如何改进。

编辑：

Input: Some array A[0..n-1] where A[i] = i
introduce(A[i], A[j]), where i≠j, is a boolean value.
For over half the values in A, introduce(A[i], A[j]) is True

Output: B ⊆ A where |B| > |A|/2 and every B[j] = some A[i] such that introduce(A[i],A[j]) is True

希望这可以更好地解释问题。

Answer 1

这可以使用Boyer–Moore majority vote algorithm在O（n）简介中完成。

考虑与会者的任意顺序：A_1，A_2，...，A_n。在算法中，您维护一个由m表示的“存储元素”。每当算法想要检查当前元素（x）是否与存储的元素相同时，就引入这两个人并相应地增加或减少计数器。最后存储的元素将是多数党的成员。然后，您可以对所有其他n-1个人进行另一次通行证，并将每个人介绍给这个已知的人，从而找到多数党的所有成员。

因此，引入的总数为O（n）。