Élément majoritaire - parties d'un tableau

Question

J'ai un tableau, rempli d'entiers. Mon travail consiste à trouver rapidement l'élément majoritaire pour n'importe quelle partie d'un tableau, et je dois le faire... temps log n Je ne suis pas linéaire, mais avant, je peux prendre le temps de préparer le tableau.

Par exemple :

1 5 2 7 7 7 8 4 6

Et des questions :

[4, 7] renvoie à 7

[4, 8] renvoie à 7

[1, 2] renvoie à 0 (pas d'élément majoritaire), et ainsi de suite...

J'ai besoin d'avoir une réponse pour chaque requête, si possible, elle doit s'exécuter rapidement.

Pour la préparation, je peux utiliser Temps O(n log n)

Answer 1

Edit : Désolé, je résolvais un autre problème.

Triez le tableau et construisez une liste ordonnée de paires (valeur, nombre_d'occurrences) - il s'agit de O(N log N). En commençant par

1 5 2 7 7 7 8 4 6

il sera

(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)

Au-dessus de ce tableau, construisez un arbre binaire avec des paires ( best_value_or_none , max_occurrences ). Cela ressemblera à :

(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)
   \   /       \   /       \  /       |
   (0,1)       (0,1)       (7,3)    (8,1)
        \     /                 \   /
         (0,1)                  (7,3)
              \                /
                     (7,3)

Cette structure a certainement un nom fantaisiste, mais je ne m'en souviens pas :)

D'ici, c'est O(log N) pour récupérer le mode d'un intervalle quelconque. Tout intervalle peut être divisé en O(log N) des intervalles précalculés, par exemple :

[4, 7] = [4, 5] + [6, 7]
f([4,5]) = (0,1)
f([6,7]) = (7,3)

et le résultat est (7,3).