TL;DR

  • Le Problème: Maîtriser le problème CTCI 10.7 avec une efficacité de niveau production.
  • L'Approche: Problème CTCI 10.7 en Java: trouver un entier absent de 4 milliards d'entiers avec une mémoire limitée.
  • Complexité: Compromis optimal entre temps et espace.

Cet article propose une explication claire et accessible du problème CTCI 10.7. Nous examinons l'énoncé, comparons l'approche brute à la solution optimale en Java.

1. Analogie du monde réel

Pensez au problème CTCI 10.7 comme à l'organisation efficace d'objets au quotidien. Choisir la bonne structure de données élimine les itérations inutiles.

2. Énoncé clair du problème

Problème 10.7: Problème CTCI 10.7 en Java: trouver un entier absent de 4 milliards d'entiers avec une mémoire limitée.

3. Approche optimale et implémentation

public class MissingInt {
    public static int findOpenNumber(Scanner scanner) {
        long numberOfInts = ((long) Integer.MAX_VALUE) + 1;
        byte[] bitfield = new byte[(int) (numberOfInts / 8)];

        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            bitfield[n / 8] |= 1 << (n % 8);
        }

        for (int i = 0; i < bitfield.length; i++) {
            for (int j = 0; j < 8; j++) {
                if ((bitfield[i] & (1 << j)) == 0) {
                    return i * 8 + j;
                }
            }
        }
        return -1;
    }
}

4. Complexité Temporelle et Spatiale

Métrique Complexité Explication
Complexité Temporelle O(N) / O(log N) Parcours optimal des données
Complexité Spatiale O(1) / O(N) Empreinte mémoire contrôlée

5. Cas Limites et Résumé

Vérifiez toujours les conditions aux limites, les valeurs nulles et la taille des tableaux en entretien.