Должен ли я использовать дерево воспроизведения?

Question

Итак, для задания нам предлагается найти псевдокод, который для данной последовательности найдет наибольшую частоту числа из последовательности. Таким образом, быстрый пример:

[1, 8, 5, 6, 6, 7, 6, 7, 6, 1, 1, 5, 8] => Число с наибольшей частотой равно 6. «Победитель» - 6.

Мы должны реализовать его в O (nlogm), где m - количество различных чисел. Итак, в приведенном выше примере имеется 5 разных чисел (m = 5).

Мой подход состоял в том, чтобы пройти через каждое число в последовательности и добавить его в двоичное дерево (если оно еще не существует) и увеличить частоту. Таким образом, для каждого номера числа в последовательности моя программа переходит к двоичному дереву, находит элемент (в logm time) и увеличивает частоту на единицу. Он регистрирует log в n раз, поэтому программа работает в 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

Вам не требуется дерево для разворота. O(n log m + m) is O(n log m) как количество отдельных элементов m не больше, чем общее количество элементов n. Таким образом, вы можете перебирать все элементы в дереве после обработки входной последовательности, чтобы найти максимум.