我应该使用八角树吗？

Question

因此，对于一项作业，我们被要求为给定序列编写一个伪代码，从该序列中找到一个数字的最大频率。所以，一个简单的例子是：

[ 1, 8, 5, 6, 6, 7, 6, 7, 6, 1, 1, 5, 8 ] => 出现次数最多的数是6，"winner"是6.

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

我的方法是遍历序列中的每个数字并将其添加到二叉树（如果还没有）并增加频率。因此，对于序列中的每个数字，我的程序都会转到二叉树，找到元素（以 logm 时间）并将频率递增 1。它执行 n 次 logm，因此程序运行时间为 O(nlogm)。然而，要找出哪个数字具有最大频率将需要另一个 O(m)。我剩下 O(nlogm + m)，通过删除低阶项，这让我剩下 O(m)，这不是教授要求的。

我记得在 class 中，为了将最常访问的项目保留在根目录中，splay 树是一个不错的选择，因此给了我 O(1) 或 O(logn)顶多给我弄个"winner"？我不知道从哪里开始实施 splay 树。

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

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);
        }
    }
}

Answer 1

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

我应该使用八角树吗？

Should I use a splay tree?

java

algorithm

tree

computer-science

binary-tree