在 O(n) 时间内确定大小为 n 的数组中超过一半的键是否是相同的键？

Question

您有一个已知大小为 n 的数组或键列表。未知此列表中有多少个唯一键，可能少至 0，多至 n。这些键没有特定的顺序，而且实际上也不可能如此，因为这些键没有大于或小于的概念，只有相等或不等的概念。现在，在你说哈希映射之前，我认为还有一个条件会影响这个想法：每个键的值都是私有的。您可以获得的有关该密钥的唯一信息是它是否与另一个密钥相同。所以基本上：

class key{
    private:
        T data;
        ...
    public:
        ...
        bool operator==(const key &k){return data==k.data}
        bool operator!=(const key &k){return data!=k.data}
};

key array[n];

现在，有没有一种算法可以在线性时间内判断数组中超过一半的键是否是相同的键？如果不是，O(n*log(n)) 又如何呢？例如，假设数组只有 3 个唯一键。数组的 60% 填充有 key.data==foo、30% key.data==bar 和 10% key.data==derp 的键。该算法只需要确定超过 50% 的键属于同一类型（data==foo 的键），并返回这些键之一。

根据我的教授的说法，这可以在 O(n) 时间内完成，但他说我们只需要找到一个可以在 O(n*log(n)) 时间内完成的任务。

Answer 1

如果您可以提取并保留任何密钥以进行进一步比较，那么Boyer-Moore 多数投票算法就是您的朋友。