1/16
révisé les pattern des problème et les ds et les algorithmes
Principe du partitionnement en deux passes (Sort Colors)
Technique de tri en place pour trois valeurs distinctes (0, 1, 2) : une premiere boucle échange et accumule tous les 0 au début via un pointeur gauche, puis une seconde boucle échange et accumule tous les 2 à la fin via un pointeur droit, laissant mécaniquement les 1 au centre.
Complexités temporelle et spatiale du tri de couleurs en deux passes
Complexité temporelle de O(n) (deux parcours complets du tableau de taille n) et complexité spatiale de O(1) (tri réalisé directement en mémoire sans tableau auxiliaire).
Rôle des pointeurs i0 et i2 dans l'algorithme Sort Colors fourni
i0 sert d'index cible pour placer le prochain élément 0 depuis le début du tableau, tandis que i2 sert d'index cible pour placer le prochain élément 2 depuis la fin du tableau.
Algorithme optimal alternatif réalisant le tri des couleurs en une seule passe
L'algorithme du drapeau hollandais (Dutch National Flag) de Dijkstra, qui utilise trois pointeurs simultanés pour classer les éléments en un seul parcours avec une complexité temporelle de O(n) et spatiale de O(1).
Comment résoudre le problème Majority Element II (éléments apparaissant \(> \lfloor n/3 \rfloor\) fois) en utilisant l'approche par Bucket Sort après avoir compté les fréquences ? (Donner les 3 grandes étapes)
Compter les occurrences de chaque nombre avec une HashMap.
Créer un tableau de listes (List<Integer>[] bucket = new List[n + 1]) où l'index représente la fréquence.
Parcourir le bucket à partir de l'index (n/3) + 1 jusqu'à la fin pour récupérer les éléments majoritaires.
for (int key : occurence.keySet()){
int value = occurence.get(key);
// ... CODE À TROUVER ...
buket[value].add(key);
}
if (buket[value] == null){
buket[value] = new ArrayList<Integer>();
}
(Note : On vérifie si la liste à cet index de fréquence existe déjà, sinon on l'initialise avant d'ajouter la clé !)
Pour trouver les éléments apparaissant plus de \(n/3\) fois, à quel index i doit commencer la boucle de collecte dans le bucket ? (Compléter le code)
int most = n / 3;
// À compléter :
for (int i = ....... ; i < buket.length; i++)
for (int i = most + 1; i < buket.length; i++)
(Explication : On cherche strictement \(> n/3\), donc on commence obligatoirement à l'entier supérieur, c'est-à-dire most + 1).
Prefix Sum
Prefix Sum est un pattern algorithmique qui consiste à utiliser un tableau auxiliaire dans lequel chaque indice contient la somme des éléments du tableau original, du premier élément jusqu'à l'indice correspondant inclus.