Mudar um Array em Java

Deslocar um array pode significar duas operações diferentes. Uma rotação move os elementos em círculo e mantém todos eles; uma rotação para a direita em duas posições leva os dois últimos elementos para o início. Já remover os elementos iniciais produz uma sequência menor e descarta esses valores. Escolha a rotação quando o array precisar manter todos os elementos; escolha a omissão quando quiser processar apenas o sufixo.

Os exemplos a seguir fazem uma rotação para a direita, salvo indicação em contrário. Uma distância positiva gira para a direita; uma distância negativa, para a esquerda. Distâncias maiores que o comprimento do array podem ser reduzidas pelo resto da divisão por esse comprimento. Arrays têm tamanho fixo, portanto o código que retorna um novo array mantém intacto o array original de quem chamou o método apenas se não o reatribuir nem modificar.

Os exemplos são programas completos em Java, e o exemplo do algoritmo de juggling inclui a saída.

Escolha entre rotacionar e remover os elementos iniciais

Use um loop ou um array temporário quando precisar de um array primitivo, como int[]. Use Collections.rotate() quando seus dados já estiverem em uma List ou quando um array de tipos de referência puder ser tratado como lista. Use o algoritmo de juggling quando precisar modificar um array sem alocar outro e puder aceitar um código mais complexo. Use skip() para descartar os primeiros n elementos de um fluxo; isso não é uma rotação e não preserva o comprimento original.

Rotacione um array no próprio lugar com um loop

Esta abordagem executa um deslocamento para a direita de cada vez. Ela guarda o último valor antes de mover os demais para a direita e, em seguida, coloca o valor guardado no índice zero. O exemplo começa com cinco inteiros e gira duas posições para a direita. Ele modifica o array recebido, usa espaço extra constante e tem complexidade de tempo O(n × k), para um array de comprimento n e uma distância normalizada k.

Execute este exemplo:
O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

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 normaliza distâncias positivas e negativas para um valor entre zero e um a menos que o comprimento do array. A verificação do comprimento evita a operação de resto por zero e mantém inalterado um array vazio. Uma distância normalizada igual a zero também não altera o array. Este método de deslocamentos repetidos é simples para distâncias pequenas; para arrays ou distâncias maiores, as duas abordagens seguintes movem cada elemento apenas uma vez.

Rotacione usando um array temporário

Aloca-se um segundo array quando se deseja um mapeamento direto de índices e há espaço para armazenamento adicional O(n). Em uma rotação para a direita, normalize primeiro a distância para steps, para que distâncias negativas ou maiores que o comprimento também funcionem. O elemento que estava no índice i vai para ((long) i + steps) % n; o valor intermediário long evita overflow na soma de índices int válidos. Se o array estiver vazio, retorne imediatamente antes de usar o operador de resto.
O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

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));
  }
}

A fórmula de destino faz com que os índices que ultrapassam a última posição voltem ao início. A soma long permanece dentro do intervalo para qualquer comprimento válido de array Java; o resto produz então um destino entre zero e values.length - 1. Somar o mesmo valor normalizado de steps módulo o comprimento do array define um mapeamento um a um: cada índice de origem corresponde a um destino distinto e a ordem relativa é preservada. O array de origem permanece inalterado; use o array retornado no lugar do original se esse for o comportamento desejado para a propriedade dos dados.

Rotacione uma lista com Collections.rotate()

Collections.rotate() opera sobre uma List: uma distância positiva gira para a direita, enquanto uma negativa gira para a esquerda. Para um array de tipos de referência, Arrays.asList(array) cria uma lista de tamanho fixo apoiada pelo próprio array. É possível substituir elementos e fazer a rotação, mas não adicionar nem remover elementos da lista. Converter a lista de volta em array cria outro array, separado. Arrays primitivos, como int[], não podem se tornar uma List<Integer> por meio de Arrays.asList; converta os valores para objetos wrapper ou use um algoritmo específico para arrays.
O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

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));
  }
}

Neste caso, a lista e values apontam para o mesmo armazenamento de elementos, então a rotação também muda a ordem dos elementos no array. O array rotated, criado separadamente, também contém os valores rotacionados. Essa opção é concisa para arrays de objetos e listas, mas converter dados primitivos para objetos wrapper exige boxing.

Rotacione no próprio lugar com o algoritmo de juggling

O algoritmo de juggling divide o array em ciclos. Em uma rotação para a esquerda de d posições, cada índice atual lê o valor do índice current + d, voltando ao zero ao ultrapassar o comprimento do array. No código, calcule esse índice sem overflow: use current >= n - d ? current - (n - d) : current + d. Como d está normalizado entre zero e n - 1, o resultado fica entre zero e n - 1; quando d é zero, o índice current permanece inalterado. O número de ciclos independentes é gcd(n, d): cada ciclo transporta os valores ao longo do seu percurso até voltar ao índice inicial. O algoritmo realiza O(n) movimentos com O(1) de espaço extra, o que pode ser útil quando não se deseja alocar outro array.
O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

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]

Primeiro, o código normaliza a distância solicitada para a direita em rightSteps; depois, converte-a na distância equivalente para a esquerda com (n - rightSteps) % n. Em um array de cinco elementos, as distâncias para a direita 2 e -2 são normalizadas para duas e três posições, produzindo distâncias para a esquerda de três e duas posições, respectivamente. Integer.MIN_VALUE também é seguro, pois é normalizado antes da subtração. Uma rotação para a esquerda lê o próximo índice de cada ciclo, voltando do fim do array ao início. O cálculo condicional no código evita somar current e leftDistance quando essa soma ultrapassaria n - 1; em qualquer dos ramos, o índice resultante fica entre zero e n - 1, mesmo se a soma direta excedesse Integer.MAX_VALUE. gcd(n, leftDistance) indica o número de ciclos. Quando a distância normalizada é zero, gcd(n, 0) é n, e o cálculo condicional retorna current, de modo que cada valor é gravado novamente na mesma posição. A verificação do comprimento trata o array vazio antes do cálculo do resto. Os métodos com loop e array temporário são mais fáceis de manter; prefira juggling quando o espaço extra constante for realmente necessário.

Omita os elementos iniciais com a Stream API

Use skip() quando quiser omitir os valores iniciais do resultado, em vez de movê-los para o fim. O método retorna um fluxo com os elementos restantes; convertê-lo em array produz um array menor e não altera a origem. Uma quantidade a omitir igual ou superior ao número de elementos resulta em uma saída vazia. skip() exige uma quantidade não negativa; valide ou limite o valor fornecido pelo chamador se ele puder ser negativo.
O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

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) cria um fluxo de inteiros, skip(count) omite os primeiros count elementos e toArray() reúne os restantes em um novo array primitivo. Isso é prático para obter um sufixo, mas aloca um resultado e não substitui a rotação quando todos os elementos precisam ser mantidos.