algorithm - 在具有隐藏元素的数组中查找多数元素

Question

我在解决这个常见问题时遇到了一些麻烦：

给定 n 个盒子，每个盒子里面有一个隐藏的数字，以及一个判断两个盒子是否包含相同或不同数字的测试程序，确定大多数盒子中是否存在一个数字，即是否有超过 n 个/2 个盒子在 O(n log n) 时间内具有相同的隐藏编号。

我知道摩尔的投票算法，但这个问题似乎略有不同。

Answer 1

您可以按原样使用 Moore 的投票算法（在 O(n) 时间和 O(1) 空间中完成）。

取自摩尔自己的网站：

我们将从起始位置向下扫描序列。

当我们扫描时，我们维护一个由当前候选人和计数器组成的对。最初，当前候选者是未知的，计数器为 0。

当我们将指针向前移动到一个元素上时e：

• 如果计数器为 0，我们将当前候选e设置为，并将计数器设置为 1。
• 如果计数器不为0，我们根据是否e是当前候选者来增加或减少计数器。

完成后，如果有多数，则当前候选人是多数元素。

稍后在该示例中：

在某些情况下，您知道或假设存在多数元素。

但是，如果您必须确认所选元素确实是多数元素，则必须再对数据进行一次线性传递才能做到这一点。

由于该算法只涉及检查当前候选是否匹配e，因此只需进行相等性检查就足够了。

要检查最终候选者是否是多数元素，只需再通过一次，将每个元素与候选者进行比较并计算匹配数。如果匹配数大于 n / 2，则您确实找到了多数元素。