4

您有一个已知大小为 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)) 时间内完成的任务。

4

3 回答 3

5

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

于 2013-02-13T05:49:32.367 回答
0

如果您不想使用 BM 算法，您可以使用基于相同思想的以下 2 种算法。

算法 A。在每次运行时，维护一组 S 的 M（N 的一小部分，例如 10）对元素计数，同时遍历每个元素的数组：

1.1. If element E is in the set, increase count of the corresponding pair (E,count) -> (E, count+1)
1.2. If not, drop out element with minimal count and insert new pair (E,1)

如果元素的频率 F > 0.5，它将在此过程结束时以概率（非常粗略，实际上要高得多）1 - (1-F)^M 出现在集合中，在第二次运行中计算元素的实际频率套。

算法 B. 取数组中随机选取的N个长度为M的元素，用任何方法选择最频繁的元素并计算它的频率和系列的中频，频率计算的最大误差为
F（realFrequency）/ sqrt（N） . 所以如果你得到 F_e* 1 - 1.0 /sqrt(N) ) > 0.5 那么你会找到最频繁的元素，如果你得到 F_e(1 + 1.0/sqrt(N)) < 0.5 这个元素不存在。F_e 是估计频率。

于 2013-02-13T08:42:28.840 回答
-2

我想到的一个解决方案是..您将从该数组中选择第一个元素，并遍历列表以及您放入单独的arraylist中的所有匹配元素，现在您从原始列表中选择第二个元素并将其与首先，如果它们相等，请留下这个元素并选择下一个。这可能是一个可能的解决方案。

于 2013-02-13T04:50:45.513 回答