Élément majoritaire

Soit $x$ majoritaire dans $T [i : j]$ , de taille $n = j - i$ , et $n_{g}$ , $n_{d}$ ses nombres d'occurrences dans les moitiés de tailles $t_{g}$ et $t_{d}$ . Si $x$ n'était majoritaire dans aucune, on aurait $n_{g} \leq t_{g} /2$ et $n_{d} \leq t_{d} /2$ , donc $n_{g} + n_{d} \leq n /2$ : $x$ ne serait pas majoritaire dans $T [i : j]$ . Contradiction.
Il n'y a donc que deux candidats : les majoritaires (éventuels) des deux moitiés. Pour chacun, on compte ses occurrences dans $T [i : j]$ .


static Integer majoritaire(int[] T, int i, int j) {   // T[i:j] non vide
    if (j - i == 1) return T[i];
    int k = (i + j) / 2;
    Integer g = majoritaire(T, i, k), d = majoritaire(T, k, j);
    if (g != null && compter(T, i, j, g) * 2 > j - i) return g;
    if (d != null && compter(T, i, j, d) * 2 > j - i) return d;
    return null;                                      // pas de majoritaire
}
static int compter(int[] T, int i, int j, int x) { int c = 0;
    for (int a = i; a < j; a++) if (T[a] == x) c++;
    return c;
}


13.10 : 2 null 4

(pour $[2, 7, 2, 2, 5, 2, 7]$ , $[1, 2, 3, 1, 2, 3]$ et $[4, 4, 1, 4]$ .) Deux appels sur des moitiés et deux comptages en $Θ (n)$ : $T (n) = 2 T (n /2) + α n$ , soit $Θ (n lo g n)$ . Il existe un algorithme séquentiel en $Θ (n)$ (vote de Boyer et Moore), écrit à partir d'un invariant astucieux.


nom : T
valeurs : 2 7 2 2 5 2 7
colorier : 0 2 3 5
pointeurs : k=3
zone : 0..2 majoritaire : 2
zone : 3..6 pas de majoritaire
legende : seul candidat 2 : 4 occurrences sur 7, et 4 × 2 > 7

Énoncé

Corrigé