Как сдвинуть элементы на n шагов в массиве

Сдвиг элементов массива на n позиций

Это классическая задача на собеседовании. Покажу несколько подходов от простых к оптимальным.

Задача

Дан массив [1, 2, 3, 4, 5]. Сдвинуть на 2 позиции вправо. Результат: [4, 5, 1, 2, 3] (циклический сдвиг) или [0, 0, 1, 2, 3] (сдвиг с нулями).

Вариант 1: Простой (через доп. массив)

public static void rotateRight(int[] arr, int n) {
    int len = arr.length;
    n = n % len;  // Если n > длины массива
    int[] temp = new int[len];
    
    for (int i = 0; i < len; i++) {
        // Элемент с индекса i идёт на индекс (i + n) % len
        temp[(i + n) % len] = arr[i];
    }
    
    // Копируем обратно
    System.arraycopy(temp, 0, arr, 0, len);
}

// Тестируем
int[] arr = {1, 2, 3, 4, 5};
rotateRight(arr, 2);
// Результат: [4, 5, 1, 2, 3]

Сложность: O(n) время, O(n) память

Плюсы: просто понимать, работает Минусы: требует доп. памяти

Вариант 2: В то же место (оптимальный)

Используем алгоритм "reversal":

1. Развернуть весь массив
2. Развернуть первые k элементов
3. Развернуть оставшиеся элементы

public static void rotateRight(int[] arr, int n) {
    n = n % arr.length;
    
    // Развернуть весь массив
    reverse(arr, 0, arr.length - 1);
    
    // Развернуть первые n
    reverse(arr, 0, n - 1);
    
    // Развернуть остаток
    reverse(arr, n, arr.length - 1);
}

private static void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Пример:
// [1, 2, 3, 4, 5], rotate(2)
// Шаг 1 (reverse all): [5, 4, 3, 2, 1]
// Шаг 2 (reverse [0:2]): [4, 5, 3, 2, 1]
// Шаг 3 (reverse [2:5]): [4, 5, 1, 2, 3]

Сложность: O(n) время, O(1) память

Это отличный ответ на собеседовании!

Вариант 3: Через Collections (если работаем с List)

public static void rotateList(List<Integer> list, int n) {
    n = n % list.size();
    Collections.rotate(list, n);
}

// Использование
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
rotateList(list, 2);
// Результат: [4, 5, 1, 2, 3]

Плюсы: одна строка, стандартная библиотека Минусы: для собеседования менее впечатляет

Вариант 4: Сдвиг влево

public static void rotateLeft(int[] arr, int n) {
    n = n % arr.length;
    
    // Развернуть весь массив
    reverse(arr, 0, arr.length - 1);
    
    // Развернуть первые (length - n)
    reverse(arr, 0, arr.length - n - 1);
    
    // Развернуть остаток
    reverse(arr, arr.length - n, arr.length - 1);
}

// Пример:
// [1, 2, 3, 4, 5], rotateLeft(2)
// Шаг 1 (reverse all): [5, 4, 3, 2, 1]
// Шаг 2 (reverse [0:3]): [3, 4, 5, 2, 1]
// Шаг 3 (reverse [3:5]): [3, 4, 5, 1, 2]

Вариант 5: С использованием Queue

public static void rotateRight(int[] arr, int n) {
    Queue<Integer> queue = new LinkedList<>();
    for (int num : arr) {
        queue.add(num);
    }
    
    // Сдвигаем n раз
    for (int i = 0; i < n % arr.length; i++) {
        queue.add(queue.poll());
    }
    
    // Копируем обратно
    int i = 0;
    for (int num : queue) {
        arr[i++] = num;
    }
}

Сложность: O(n) время, O(n) память

Плюсы: интуитивно понимается Минусы: требует доп. памяти

Вариант 6: Циклические сдвиги (сложный случай)

Если массив [1, 2, 2, 3]:

public static void rotateRightOptimized(int[] arr, int n) {
    n = n % arr.length;
    if (n == 0) return;
    
    int gcd = gcd(arr.length, n);
    
    for (int i = 0; i < gcd; i++) {
        int current = i;
        int temp = arr[i];
        
        while (true) {
            int next = (current + n) % arr.length;
            if (next == i) break;
            
            arr[current] = arr[next];
            current = next;
        }
        arr[current] = temp;
    }
}

private static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Это минимизирует количество обращений к памяти. Сложность: O(n) время, O(1) память

Тесты

public class RotateArrayTest {
    
    @Test
    public void testRotateRight() {
        int[] arr = {1, 2, 3, 4, 5};
        rotateRight(arr, 2);
        assertArrayEquals(new int[]{4, 5, 1, 2, 3}, arr);
    }
    
    @Test
    public void testRotateZero() {
        int[] arr = {1, 2, 3, 4, 5};
        rotateRight(arr, 0);
        assertArrayEquals(new int[]{1, 2, 3, 4, 5}, arr);
    }
    
    @Test
    public void testRotateMoreThanLength() {
        int[] arr = {1, 2, 3, 4, 5};
        rotateRight(arr, 7);  // 7 % 5 = 2
        assertArrayEquals(new int[]{4, 5, 1, 2, 3}, arr);
    }
    
    @Test
    public void testSingleElement() {
        int[] arr = {1};
        rotateRight(arr, 5);
        assertArrayEquals(new int[]{1}, arr);
    }
}

Мой рекомендуемый ответ на собеседовании

1. Сначала спрашиваю: циклический сдвиг или со сдвигом в нули?
2. Предлагаю вариант 1 (простой с доп. массивом) — показываю, что понимаю логику
3. Затем оптимизирую до варианта 2 (reversal) — показываю, что думаю о памяти
4. Объясняю сложность: O(n) время, O(1) память
5. Обсуждаю граничные случаи (n = 0, n > length, пустой массив)

Это покажет, что вы не только решили задачу, но и думаете о оптимизации и edge case.