Description du problème

Dans une matrice de dimensions n × m, un nombre apparaît plus de la moitié des fois. Concevez un algorithme efficace pour identifier ce nombre.

Format d'entrée : La première ligne contient deux entiers n et m représentant la taille de la matrice (1≤n,m≤10^3). Les n lignes suivantes contiennent chacune m entiers positifs correspondant aux éléments de la matrice.

Format de sortie : Afficher un entier, le nombre qui apparaît plus de la moitié des fois dans la matrice.

Exemple d'entrée :
3 3
1 2 3
2 2 2
1 2 2

Exemple de sortie :
2

Solution 1 : Utliisation de l'algorithme de vote de Boyer-Moore

Analyse

Cette approche adapte l'algorithme de vote de Boyer-Moore pour trouver un candidat potentiel, puis vérifie s'il représente effectivement la majorité.

Code clé

La méthode detecterElementMajoritaire prend une matrice 2D, la transforme en tableau linéaire, identifie un candidat et le valide.

private static int detecterElementMajoritaire(int[][] matrice) {
    if (matrice == null || matrice.length == 0 || matrice[0].length == 0) {
        return -1;
    }
    int[] tableauLineaire = aplatirMatrice(matrice);
    int candidat = trouverCandidat(tableauLineaire);
    return verifierMajorite(candidat, tableauLineaire) ? candidat : -1;
}

Méthode aplatirMatrice : Convertit la matrice 2D en un tableau 1D.

private static int[] aplatirMatrice(int[][] matrice) {
    int lignes = matrice.length;
    int colonnes = matrice[0].length;
    int[] tableau = new int[lignes * colonnes];
    int index = 0;
    for (int i = 0; i < lignes; i++) {
        for (int j = 0; j < colonnes; j++) {
            tableau[index++] = matrice[i][j];
        }
    }
    return tableau;
}

Méthode trouverCandidat : Implémente l'algorithme de vote pour déterminer un candidat. Parcourt le tableau, en maintenatn un compteur pour le candidat actuel. Si le compteur tombe à zéro, un nouveau candidat est sélectionné.

private static int trouverCandidat(int[] donnees) {
    int compteur = 0;
    int potentiel = -1;
    for (int valeur : donnees) {
        if (compteur == 0) {
            potentiel = valeur;
        }
        compteur += (valeur == potentiel) ? 1 : -1;
    }
    return potentiel;
}

Méthode verifierMajorite : Vérifie si le candidat apparaît plus de la moitié des fois dans le tableau.

private static boolean verifierMajorite(int candidat, int[] donnees) {
    int occurrences = 0;
    for (int valeur : donnees) {
        if (valeur == candidat) {
            occurrences++;
        }
    }
    return occurrences > donnees.length / 2;
}

Complexité temporelle

La conversion en tableau linéaire prend O(nm). La recherche du candidat parcourt le tableau, soit O(nm). La vérification nécessite également O(nm). La compelxité totale est donc O(3nm).

Solution 2 : Utilisation d'une table de hachage

Analyse

Cette méthode optimisée emploie une table de hachage pour compter les occurrences de chaque nombre et identifier directement celui qui dépasse la moitié.

Code clé

Création d'une table de hachage pour stocker les comptes et recherche du nombre majoritaire.

Map<Integer, Integer> compteur = new HashMap<>();
for (int i = 0; i < n * m; i++) {
    int element = scanner.nextInt();
    compteur.put(element, compteur.getOrDefault(element, 0) + 1);
}

for (Map.Entry<Integer, Integer> entree : compteur.entrySet()) {
    if (entree.getValue() * 2 > n * m) {
        System.out.println(entree.getKey());
    }
}

Complexité temporelle

La lecture des éléments et la mise à jour de la table de hachage s'effectuent en O(nm). L'itération sur les entrées de la table est également O(nm). La complexité globale est O(nm).