La maîtrise des structures de données linéaires et bidimensionnelles est fondamentale en C et C++. Voici une exploration détaillée des algorithmes essentiels pour la manipulation de tableaux et de matrices, optimisés pour la performance et la lisibilité.

1. Inversion d'un tableau

L'inversion d'une séquence peut être réalisée de manière optimale en utilisant l'approche des deux pointeurs en C, ou en tirant parti de la bibliothèque stnadard en C++.

// Implémentation en C avec arithmétique de pointeurs
#include <stdio.h>

void inverser_tableau(int *debut, int *fin) {
    while (debut < fin) {
        int temporaire = *debut;
        *debut++ = *fin;
        *fin-- = temporaire;
    }
}

int main() {
    int donnees[] = {10, 20, 30, 40, 50, 60, 70};
    int taille = sizeof(donnees) / sizeof(donnees[0]);
    
    inverser_tableau(donnees, donnees + taille - 1);
    
    for (int i = 0; i < taille; i++) {
        printf("%d ", donnees[i]);
    }
    return 0;
}

// Implémentation moderne en C++
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> sequence = {10, 20, 30, 40, 50, 60};
    
    std::reverse(sequence.begin(), sequence.end());
    
    for (const auto& val : sequence) {
        std::cout << val << " ";
    }
    return 0;
}

2. Insertino dans un tableau trié

Pour insérer un élément tout en conservant l'ordre, il est préférable d'utiliser la recherche dichotomique pour loclaiser la position, puis de décaler les éléments.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> collection = {2, 5, 8, 12, 19, 25, 30};
    int nouvelle_valeur = 15;
    
    // lower_bound trouve le premier élément qui n'est pas inférieur à la valeur
    auto it = std::lower_bound(collection.begin(), collection.end(), nouvelle_valeur);
    collection.insert(it, nouvelle_valeur);
    
    for (int num : collection) {
        std::cout << num << " ";
    }
    return 0;
}

3. Rotation de matrice à 90 degrés

La rotation d'une matrice carrée sur place s'effectue en deux étapes : la transposition de la matrice, suivie de l'inversion de chaque ligne.

#include <iostream>
#include <vector>
#include <algorithm>

void pivoter_matrice(std::vector<std::vector<int>>& grille) {
    int dimension = grille.size();
    
    // Étape 1 : Transposition
    for (int ligne = 0; ligne < dimension; ++ligne) {
        for (int col = ligne + 1; col < dimension; ++col) {
            std::swap(grille[ligne][col], grille[col][ligne]);
        }
    }
    
    // Étape 2 : Inversion des lignes
    for (int ligne = 0; ligne < dimension; ++ligne) {
        std::reverse(grille[ligne].begin(), grille[ligne].end());
    }
}

int main() {
    std::vector<std::vector<int>> matrice = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    pivoter_matrice(matrice);
    
    for (const auto& rang : matrice) {
        for (int val : rang) std::cout << val << " ";
        std::cout << "\n";
    }
    return 0;
}

4. Mise à zéro de la matrice

L'algorithme optimal utilise la première ligne et la première colonne comme indicateurs (flags) pour atteindre une complexité spatiale de O(1).

#include <iostream>
#include <vector>

void definir_zeros(std::vector<std::vector<int>>& matrice) {
    if (matrice.empty()) return;
    int lignes = matrice.size(), colonnes = matrice[0].size();
    bool premiere_ligne_zero = false, premiere_colonne_zero = false;

    for (int i = 0; i < lignes; ++i) if (matrice[i][0] == 0) premiere_colonne_zero = true;
    for (int j = 0; j < colonnes; ++j) if (matrice[0][j] == 0) premiere_ligne_zero = true;

    for (int i = 1; i < lignes; ++i) {
        for (int j = 1; j < colonnes; ++j) {
            if (matrice[i][j] == 0) {
                matrice[i][0] = 0;
                matrice[0][j] = 0;
            }
        }
    }

    for (int i = 1; i < lignes; ++i) {
        for (int j = 1; j < colonnes; ++j) {
            if (matrice[i][0] == 0 || matrice[0][j] == 0) {
                matrice[i][j] = 0;
            }
        }
    }

    if (premiere_colonne_zero) for (int i = 0; i < lignes; ++i) matrice[i][0] = 0;
    if (premiere_ligne_zero) for (int j = 0; j < colonnes; ++j) matrice[0][j] = 0;
}

5. Recherche dans une matrice 2D

Si la matrice est triée de manière globale (chaque ligne et colonne est triée, et le premier élément d'une ligne est supérieur au dernier de la précédente), on peut l'aplatir virtuellement pour appliquer une recherche dichotomique.

#include <vector>

bool rechercher_cible(const std::vector<std::vector<int>>& grille, int cible) {
    if (grille.empty() || grille[0].empty()) return false;
    int nb_lignes = grille.size(), nb_cols = grille[0].size();
    int gauche = 0, droite = nb_lignes * nb_cols - 1;

    while (gauche <= droite) {
        int milieu = gauche + (droite - gauche) / 2;
        int valeur_milieu = grille[milieu / nb_cols][milieu % nb_cols];

        if (valeur_milieu == cible) return true;
        if (valeur_milieu < cible) gauche = milieu + 1;
        else droite = milieu - 1;
    }
    return false;
}

6. Somme de deux nombres (Two Sum)

L'utilisation d'une table de hachage permet de réduire la complexité temporelle à O(n) en stockant les compléments nécessaires.

#include <vector>
#include <unordered_map>

std::vector<int> trouver_indices(const std::vector<int>& nombres, int objectif) {
    std::unordered_map<int, int> registre;
    
    for (int i = 0; i < nombres.size(); ++i) {
        int complement = objectif - nombres[i];
        if (registre.count(complement)) {
            return {registre[complement], i};
        }
        registre[nombres[i]] = i;
    }
    return {};
}

7. Parcours en spirale d'une matrice

Le parcours en spirale nécessite la gestion de quatre limites dynamiques qui se contractent vers le centre de la matrice.

#include <vector>

std::vector<int> parcours_spirale(const std::vector<std::vector<int>>& matrice) {
    std::vector<int> resultat;
    if (matrice.empty()) return resultat;
    
    int haut = 0, bas = matrice.size() - 1;
    int gauche = 0, droite = matrice[0].size() - 1;

    while (haut <= bas && gauche <= droite) {
        for (int i = gauche; i <= droite; ++i) resultat.push_back(matrice[haut][i]);
        haut++;
        for (int i = haut; i <= bas; ++i) resultat.push_back(matrice[i][droite]);
        droite--;
        
        if (haut <= bas) {
            for (int i = droite; i >= gauche; --i) resultat.push_back(matrice[bas][i]);
            bas--;
        }
        if (gauche <= droite) {
            for (int i = bas; i >= haut; --i) resultat.push_back(matrice[i][gauche]);
            gauche++;
        }
    }
    return resultat;
}

8. Somme de trois nombres (3Sum)

Après un tri initial, on fixe un élément et on utilise deux pointeurs pour trouver les paires restantes, en veillant à ignorer les doublons.

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> triplets_zero(std::vector<int>& nums) {
    std::vector<std::vector<int>> solutions;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();

    for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int ptr_gauche = i + 1, ptr_droit = n - 1;

        while (ptr_gauche < ptr_droit) {
            int somme = nums[i] + nums[ptr_gauche] + nums[ptr_droit];
            if (somme == 0) {
                solutions.push_back({nums[i], nums[ptr_gauche], nums[ptr_droit]});
                while (ptr_gauche < ptr_droit && nums[ptr_gauche] == nums[ptr_gauche + 1]) ptr_gauche++;
                while (ptr_gauche < ptr_droit && nums[ptr_droit] == nums[ptr_droit - 1]) ptr_droit--;
                ptr_gauche++; ptr_droit--;
            } else if (somme < 0) {
                ptr_gauche++;
            } else {
                ptr_droit--;
            }
        }
    }
    return solutions;
}

9. Somme de quatre nombres (4Sum)

Extension du problème précédent, nécessitant une boucle imbriquée supplémentaire et des conditions d'élagage pour optimiser l'exécution.

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> quadruplets(std::vector<int>& nums, int cible) {
    std::vector<std::vector<int>> res;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();

    for (int i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            
            int g = j + 1, d = n - 1;
            while (g < d) {
                long long somme = (long long)nums[i] + nums[j] + nums[g] + nums[d];
                if (somme == cible) {
                    res.push_back({nums[i], nums[j], nums[g], nums[d]});
                    while (g < d && nums[g] == nums[g + 1]) g++;
                    while (g < d && nums[d] == nums[d - 1]) d--;
                    g++; d--;
                } else if (somme < cible) {
                    g++;
                } else {
                    d--;
                }
            }
        }
    }
    return res;
}

10. Suppression de doublons (Maximum 2 occurrences)

L'algorithme de modification sur place utilise un pointeur d'écriture qui ne progresse que si l'élément actuel diffère de l'élément situé deux positions en arrière.

#include <vector>

int conserver_doublons(std::vector<int>& donnees) {
    int taille = donnees.size();
    if (taille <= 2) return taille;
    
    int index_ecriture = 2;
    for (int index_lecture = 2; index_lecture < taille; ++index_lecture) {
        if (donnees[index_lecture] != donnees[index_ecriture - 2]) {
            donnees[index_ecriture++] = donnees[index_lecture];
        }
    }
    return index_ecriture;
}

11. Suppression totale des doublons

Pour ne conserver que des éléments strictement uniques, le pointeur d'écriture compare l'élément actuel avec le dernier élément validé.

#include <vector>

int elements_uniques(std::vector<int>& donnees) {
    if (donnees.empty()) return 0;
    
    int index_ecriture = 0;
    for (int index_lecture = 1; index_lecture < donnees.size(); ++index_lecture) {
        if (donnees[index_lecture] != donnees[index_ecriture]) {
            donnees[++index_ecriture] = donnees[index_lecture];
        }
    }
    return index_ecriture + 1;
}