我应该使用八卦树吗？

debugcn 发表于 Dev

妈妈

因此，对于一项分配，我们要求查找针对给定序列编写的伪代码，并从该序列中找到数字的最大频率。因此，一个简单的例子是：

[1，8，5，6，6，7，6，6，1，1，5，8] =>出现频率最高的数字是6。“获胜者”是6。

我们必须在O（nlogm）时间实现它，其中m是不同数字的数量。因此，在上面的示例中，有5个不同的数字（m = 5）。

我的方法是遍历序列中的每个数字，并将其添加到二叉树中（如果尚不存在）并增加频率。因此，对于序列中的每个数字，我的程序都转到二叉树，找到元素（以logm时间表示）并将频率增加1。它确实执行n次logm，因此程序在O（nlogm）中运行。但是，要找出频率最大的数字又要花费O（m）。我剩下O（nlogm + m），通过删除低阶术语使我剩下O（m），这不是教授所要的。

我从课堂上记得，为了将最常访问的项保留在根目录上，使用展开树将是一个很好的选择，因此给我O（1）或最多O（logn）来使我成为“赢家” ？我不知道从哪里开始实现八叉树。

如果您能提供任何见解，我将不胜感激。

public E theWinner(E[] C) {
    int i = 0;
    while (i < C.length) {
        findCandidate(C[i], this.root);
    }
    // This is where I'm stuck, returning the winner in < O(n) time.

}

public void findNumber(E number, Node<E> root) {
    if (root.left == null && root.right == null) {
        this.add(number); 
        //splay tree?
    } else if (root.data.compareTo(number) == 0) {
        root.freqCount = root.freqCount + 1;
        //splay tree?
    } else {
        if ( root.data.compareTo(number) < 0) {
            findNumber(number, root.right);
        } else {
            findNumber(number, root.left);
        }
    }
}

克拉斯科维奇

您不需要八卦树。O(n log m + m)是O(n log m)因为不同元素的数量m不大于元素的总数n。因此，您可以在处理输入序列以找到最大值之后遍历树中的所有元素。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。