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

所以，对于一个赋值，我们需要找到一个伪代码，对于给定的序列，从序列中找出一个数字的最大频率。一个简单的例子是：
[1、8、5、6、6、7、6、7、6、1、1、5、8]=>频率最大的数字是6“赢家”是6。
我们必须在o（nlogm）时间内实现它，其中m是不同数的个数。所以，在上面的例子中，有5个不同的数字（m=5）。
我的方法是遍历序列中的每个数字，并将其添加到二叉树（如果还没有）中，然后增加频率因此，对于序列中的每一个数字，我的程序进入二叉树，找到元素（以logm时间为单位）并将频率增加一。它在n次中执行logm，所以程序在o（nlogm）中运行。然而，要找出哪个数字的频率最大，还需要0（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);
        }
    }
}

最佳答案

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