java - 我应该使用八角树吗？

Question

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

[ 1, 8, 5, 6, 6, 7, 6, 7, 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)，这不是教授要求的。

我记得在类里面，为了将最常访问的项目保留在根目录中，splay 树是一个很好的选择，因此最多给我 O(1) 或 O(logn) 来让我“优胜者”？我不知道从哪里开始实现 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

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