Dans ce problème, nous avons un tableau d'entiers où tous les éléments appaarissent exactemant deux fois, excepté un seul qui n'apparaît qu'une fois. L'objectif est d'identifier ce nombre unique efficacement.

Exigences :

• La solution doit avoir une complexité temporelle de O(n).
• L'utilisation d'espace mémoire supplémentaire doit être minimisée.

Exemples

• 1 ≤ taille du tableau ≤ 1001
• 0 ≤ valeurs ≤ 1000
• La taille du tableau est impaire.
• À l'exception d'un nombre, tous les autres sont présents exactement deux fois.

Solutions

Approche 1 : Tri et Parcours Séquentiel

Cette méthode implique de trier le tableau, puis de parcourir pour trouver l'élément qui diffère de ses voisins. Bien que simple, elle a une complexité temporelle de O(n log n) due au tri.

import java.util.Arrays;

public class RechercheNombreUnique {
    public static int localiser(int[] donnees) {
        Arrays.sort(donnees);
        
        if (donnees.length == 1 || donnees[0] != donnees[1]) {
            return donnees[0];
        }
        
        if (donnees[donnees.length - 1] != donnees[donnees.length - 2]) {
            return donnees[donnees.length - 1];
        }
        
        for (int idx = 1; idx < donnees.length - 1; idx++) {
            if (donnees[idx] != donnees[idx - 1] && donnees[idx] != donnees[idx + 1]) {
                return donnees[idx];
            }
        }
        throw new IllegalArgumentException("Aucune valeur unique détectée");
    }

    public static void main(String[] args) {
        System.out.println(localiser(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(localiser(new int[]{0, 1, 0, 1, 2}) == 2);
    }
}

Approche 2 : Table de Hachage pour le Comptage

En utilisant une structure de données de type dictionnaire, nous comptons les occurrences de chaque élément, puis recherchons celui avec un cmopteur égal à un.

import java.util.HashMap;
import java.util.Map;

public class RechercheNombreUnique {
    public static int localiser(int[] donnees) {
        Map<Integer, Integer> occurrences = new HashMap<>();
        
        for (int val : donnees) {
            occurrences.merge(val, 1, Integer::sum);
        }
        
        for (Map.Entry<Integer, Integer> entree : occurrences.entrySet()) {
            if (entree.getValue() == 1) {
                return entree.getKey();
            }
        }
        throw new IllegalArgumentException("Aucune valeur unique détectée");
    }

    public static void main(String[] args) {
        System.out.println(localiser(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(localiser(new int[]{0, 1, 0, 1, 2}) == 2);
    }
}

Approche 3 : Opération Bitwise XOR

Cette solution exploite les propriétés du XOR : a XOR a = 0 et a XOR 0 = a. En appliquant XOR sur tous les éléments, les doublons s'annulent, laissant le nombre unique.

public class RechercheNombreUnique {
    public static int localiser(int[] donnees) {
        int resultat = 0;
        for (int element : donnees) {
            resultat ^= element;
        }
        return resultat;
    }

    public static void main(String[] args) {
        System.out.println(localiser(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(localiser(new int[]{0, 1, 0, 1, 2}) == 2);
    }
}