Déplacer un tableau en Java

Le déplacement d’un tableau peut désigner deux opérations différentes. Une rotation fait circuler les éléments tout en les conservant tous : une rotation vers la droite de deux positions place les deux derniers éléments au début. À l’inverse, supprimer les premiers éléments renvoie une séquence plus courte et élimine ces valeurs. Choisissez la rotation si le tableau doit conserver son contenu, et la suppression des premiers éléments si vous souhaitez traiter uniquement le suffixe.

Sauf indication contraire, les exemples effectuent une rotation vers la droite. Une distance positive entraîne une rotation vers la droite, une distance négative vers la gauche, et les distances supérieures à la longueur du tableau peuvent être réduites modulo cette longueur. Les tableaux ont une longueur fixe : le code qui renvoie un nouveau tableau laisse celui d’origine intact uniquement si vous ne le réaffectez pas et ne le modifiez pas.

Les exemples sont des programmes Java autonomes ; la sortie de l’exemple de l’algorithme par cycles est également présentée. Les libellés affichés par les exemples restent en anglais ; les valeurs permettent de suivre le résultat.

Choisir entre une rotation et la suppression des premiers éléments

Pour un tableau de types primitifs comme int[], utilisez une boucle ou un tableau temporaire. Utilisez Collections.rotate() si vos données sont déjà dans une List ou si un tableau de types référence peut être utilisé comme liste. Si vous devez modifier le tableau sans en allouer un autre et acceptez un code plus complexe, choisissez l’algorithme par cycles. Utilisez skip() pour éliminer les n premiers éléments d’un flux : ce n’est pas une rotation et le résultat ne conserve pas la longueur initiale.

Faire pivoter un tableau en place avec une boucle

Cette méthode effectue un décalage vers la droite à la fois. Elle sauvegarde la dernière valeur avant de déplacer les autres vers la droite, puis place la valeur sauvegardée à l’indice zéro. L’exemple part de cinq entiers et effectue une rotation de deux positions vers la droite. Il modifie le tableau fourni, utilise un espace supplémentaire constant et s’exécute en O(n × k), où n est la longueur du tableau et k la distance normalisée.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int step = 0; step < steps; step++) {
        int last = values[values.length - 1];
        for (int i = values.length - 1; i > 0; i--) {
          values[i] = values[i - 1];
        }
        values[0] = last;
      }
    }
    System.out.println(Arrays.toString(values));
  }
}

Math.floorMod normalise les distances positives et négatives en une valeur comprise entre zéro et la longueur du tableau moins un. Le contrôle de la longueur évite une division modulo zéro et laisse un tableau vide inchangé. Une distance normalisée égale à zéro ne modifie pas non plus le tableau. Cette méthode par décalages répétés est simple lorsque la distance est faible ; pour les grands tableaux ou les grandes distances, les deux méthodes suivantes déplacent chaque élément une seule fois.

Faire pivoter un tableau dans un tableau temporaire

Allouez un second tableau si vous souhaitez associer directement les indices et pouvez utiliser O(n) d’espace supplémentaire. Pour une rotation vers la droite, normalisez d’abord la distance en steps afin de prendre en charge les distances négatives et supérieures à la longueur du tableau. L’élément situé à l’ancien indice i est placé à ((long) i + steps) % n ; l’intermédiaire long évite un dépassement lors de l’addition d’indices int valides. Si le tableau est vide, retournez immédiatement avant d’effectuer l’opération modulo.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    int[] rotated = new int[values.length];
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int i = 0; i < values.length; i++) {
        int destination = (int) (((long) i + steps) % values.length);
        rotated[destination] = values[i];
      }
    }
    System.out.println(Arrays.toString(rotated));
  }
}

La formule de destination ramène au début les indices qui dépassent la dernière position. La somme de type long reste dans les limites pour toute longueur valide de tableau Java ; l’opération modulo produit ensuite une destination comprise entre zéro et values.length - 1. Ajouter le même steps normalisé modulo la longueur du tableau définit une correspondance bijective : chaque indice source aboutit à une destination distincte et l’ordre relatif est conservé. Le tableau source reste inchangé ; si vous souhaitez utiliser le résultat à sa place, servez-vous du tableau renvoyé.

Faire pivoter une liste avec Collections.rotate()

Collections.rotate() s’applique à une List : une distance positive fait pivoter la liste vers la droite et une distance négative vers la gauche. Pour un tableau de types référence, Arrays.asList(array) crée une liste de taille fixe adossée au même tableau : ses éléments peuvent être remplacés et la rotation fonctionne, mais l’ajout et la suppression d’éléments ne sont pas pris en charge. Convertir ensuite la liste en tableau produit un tableau distinct. Les tableaux de types primitifs comme int[] ne peuvent pas être convertis en List<Integer> avec Arrays.asList ; convertissez les valeurs en objets enveloppes ou choisissez un algorithme adapté aux tableaux.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    Integer[] values = {1, 2, 3, 4, 5};
    List<Integer> list = Arrays.asList(values);
    Collections.rotate(list, 2);
    Integer[] rotated = list.toArray(new Integer[0]);
    System.out.println(Arrays.toString(rotated));
  }
}

Ici, la liste et values désignent le même stockage d’éléments ; la rotation change donc aussi l’ordre des éléments du tableau. Le tableau rotated, créé séparément, contient lui aussi les valeurs pivotées. Cette approche est concise pour les tableaux d’objets et les listes, mais convertir des données primitives en objets enveloppes entraîne une mise en boîte.

Faire pivoter un tableau en place avec l’algorithme par cycles

L’algorithme par cycles répartit le tableau en cycles. Pour une rotation vers la gauche de d positions, chaque indice courant lit la valeur à l’indice current + d, en revenant au début lorsque l’indice atteint la longueur du tableau. Pour calculer cet indice sans dépassement, utilisez current >= n - d ? current - (n - d) : current + d. Comme d est normalisé entre zéro et n - 1, le résultat est compris entre zéro et n - 1 ; si d vaut zéro, l’indice current reste inchangé. Le nombre de cycles indépendants est gcd(n, d) : chaque cycle déplace les valeurs le long de son parcours jusqu’à retrouver son indice de départ. L’algorithme effectue O(n) déplacements avec O(1) d’espace supplémentaire ; il peut être utile lorsqu’il est important de ne pas allouer un autre tableau.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int rightDistance = 2;
    int n = values.length;
    if (n > 0) {
      int rightSteps = Math.floorMod(rightDistance, n);
      int leftDistance = (n - rightSteps) % n;
      int cycles = gcd(n, leftDistance);
      for (int start = 0; start < cycles; start++) {
        int saved = values[start];
        int current = start;
        while (true) {
          int next = current >= n - leftDistance
              ? current - (n - leftDistance)
              : current + leftDistance;
          if (next == start) break;
          values[current] = values[next];
          current = next;
        }
        values[current] = saved;
      }
    }
    System.out.println(Arrays.toString(values));
  }

  private static int gcd(int a, int b) {
    while (b != 0) {
      int remainder = a % b;
      a = b;
      b = remainder;
    }
    return a;
  }
}

[4, 5, 1, 2, 3]

Le code normalise d’abord la distance demandée vers la droite en rightSteps, puis la convertit en distance équivalente vers la gauche avec (n - rightSteps) % n. Pour un tableau de cinq éléments, les distances vers la droite 2 et -2 sont normalisées en deux et trois pas vers la droite ; elles correspondent respectivement à trois et deux pas vers la gauche. Integer.MIN_VALUE est également pris en charge, car la distance est normalisée avant la soustraction. Une rotation vers la gauche lit la valeur de l’indice suivant dans chaque cycle et revient au début après la fin du tableau. Le calcul conditionnel du code évite d’additionner current et leftDistance lorsque leur somme dépasserait n - 1 ; dans les deux branches, le résultat reste compris entre zéro et n - 1, même si la somme directe dépasserait Integer.MAX_VALUE. gcd(n, leftDistance) donne le nombre de cycles. Lorsque la distance normalisée est zéro, gcd(n, 0) vaut n et le calcul conditionnel renvoie current : chaque valeur est donc réécrite à son emplacement. Le contrôle de longueur prend en charge le tableau vide avant le calcul modulo. Les méthodes avec boucle ou tableau temporaire sont plus faciles à maintenir ; privilégiez l’algorithme par cycles lorsque son espace supplémentaire constant répond à un besoin réel.

Écarter les premiers éléments avec l’API Stream

Utilisez skip() lorsque les premières valeurs doivent être omises du résultat au lieu d’être déplacées à la fin. La méthode renvoie un flux contenant les éléments restants ; convertir ce flux en tableau produit donc un tableau plus court sans modifier la source. Si le nombre d’éléments à écarter est égal ou supérieur au nombre d’éléments du flux, le résultat est vide. skip() exige un nombre non négatif ; validez ou limitez la valeur fournie par l’appelant si elle peut être négative.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    long count = 2;
    int[] remainder = Arrays.stream(values).skip(count).toArray();
    System.out.println(Arrays.toString(remainder));
  }
}

Arrays.stream(values) crée un flux d’entiers, skip(count) en omet les count premiers éléments, et toArray() rassemble les éléments restants dans un nouveau tableau de types primitifs. C’est pratique pour obtenir un suffixe, mais cette opération alloue un résultat et ne remplace pas une rotation lorsque tous les éléments doivent être conservés.