Поворот массива на K позиций

Поворот массива на K позиций

Объяснение задачи

Нужно повернуть массив вправо на k позиций на месте (in-place), без использования дополнительной памяти.

Пример: [1, 2, 3, 4, 5, 6, 7] при k=3 становится [5, 6, 7, 1, 2, 3, 4]

Решение 1: Метод трёх разворотов (самое оптимальное)

Идея: развернуть три части массива в определённом порядке:

public class ArrayRotation {
    /**
     * Поворот массива на k позиций
     * Время: O(n), Память: O(1)
     * Идея: reverse весь массив, потом первые k, потом оставшиеся
     */
    public static void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        // Нормализуем k, так как k > длины эквивалентно k % длины
        k = k % nums.length;
        
        // Развернуть весь массив
        reverse(nums, 0, nums.length - 1);
        
        // Развернуть первые k элементов
        reverse(nums, 0, k - 1);
        
        // Развернуть оставшиеся элементы
        reverse(nums, k, nums.length - 1);
    }
    
    /**
     * Вспомогательный метод для разворота части массива
     */
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Как работает пошагово:

Исходный массив: [1, 2, 3, 4, 5, 6, 7], k = 3

Шаг 1: Развернуть весь массив
[7, 6, 5, 4, 3, 2, 1]

Шаг 2: Развернуть первые k=3 элементов
[5, 6, 7, 4, 3, 2, 1]

Шаг 3: Развернуть оставшиеся элементы (индекс 3 до конца)
[5, 6, 7, 1, 2, 3, 4]

Результат: [5, 6, 7, 1, 2, 3, 4] ✓

Математическое объяснение:

• После первого разворота элементы находятся в обратном порядке
• Разворот первых k и последних (n-k) элементов восстанавливает нужное расположение

Решение 2: Циклический сдвиг (простое для понимания)

public class ArrayRotation {
    /**
     * Поворот через циклический сдвиг
     * Время: O(n), Память: O(1)
     */
    public static void rotateShift(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        k = k % nums.length;
        
        // Сдвигаем каждый элемент на k позиций
        for (int i = 0; i < k; i++) {
            // Сдвиг на 1 позицию k раз
            shiftByOne(nums);
        }
    }
    
    /**
     * Сдвинуть массив вправо на 1 позицию
     */
    private static void shiftByOne(int[] nums) {
        int last = nums[nums.length - 1];
        for (int i = nums.length - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        nums[0] = last;
    }
}

Минус: время O(n * k), что медленнее при больших k.

Решение 3: С использованием дополнительного массива (для сравнения)

public class ArrayRotation {
    /**
     * Поворот с использованием доп. массива
     * Время: O(n), Память: O(n)
     */
    public static void rotateWithArray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        k = k % nums.length;
        int[] rotated = new int[nums.length];
        
        // Новая позиция элемента: (i + k) % length
        for (int i = 0; i < nums.length; i++) {
            rotated[(i + k) % nums.length] = nums[i];
        }
        
        // Скопировать обратно
        System.arraycopy(rotated, 0, nums, 0, nums.length);
    }
}

Решение 4: Использование Collections (для больших объектов)

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

public class ArrayRotation {
    public static void rotateCollections(List<Integer> nums, int k) {
        int n = nums.size();
        k = k % n;
        
        // Collections.rotate встроена, но работает с O(n) в худшем случае
        Collections.rotate(nums, k);
    }
}

Полные тесты

public class ArrayRotationTest {
    public static void main(String[] args) {
        // Тест 1: Базовый случай
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7};
        rotate(nums1, 3);
        System.out.println("Test 1: " + Arrays.toString(nums1));
        // Ожидается: [5, 6, 7, 1, 2, 3, 4]
        
        // Тест 2: k больше длины
        int[] nums2 = {-1, -100, 3, 99};
        rotate(nums2, 2);
        System.out.println("Test 2: " + Arrays.toString(nums2));
        // Ожидается: [3, 99, -1, -100]
        
        // Тест 3: k равна длине
        int[] nums3 = {1, 2, 3, 4};
        rotate(nums3, 4);
        System.out.println("Test 3: " + Arrays.toString(nums3));
        // Ожидается: [1, 2, 3, 4]
        
        // Тест 4: k > длины (нужна нормализация)
        int[] nums4 = {1, 2, 3, 4, 5};
        rotate(nums4, 7);  // 7 % 5 = 2
        System.out.println("Test 4: " + Arrays.toString(nums4));
        // Ожидается: [4, 5, 1, 2, 3]
        
        // Тест 5: k = 0
        int[] nums5 = {1, 2, 3};
        rotate(nums5, 0);
        System.out.println("Test 5: " + Arrays.toString(nums5));
        // Ожидается: [1, 2, 3]
        
        // Тест 6: Массив из одного элемента
        int[] nums6 = {1};
        rotate(nums6, 5);
        System.out.println("Test 6: " + Arrays.toString(nums6));
        // Ожидается: [1]
    }
    
    static void rotate(int[] nums, int k) {
        ArrayRotation.rotate(nums, k);
    }
}

Edge Cases и обработка

public class EdgeCaseTests {
    public static void main(String[] args) {
        // Edge case 1: Пустой массив
        int[] empty = {};
        ArrayRotation.rotate(empty, 5);
        System.out.println("Empty: " + Arrays.toString(empty));
        
        // Edge case 2: k = 0
        int[] nums = {1, 2, 3};
        ArrayRotation.rotate(nums, 0);
        System.out.println("k=0: " + Arrays.toString(nums));
        
        // Edge case 3: k кратно длине
        int[] nums2 = {1, 2, 3, 4};
        ArrayRotation.rotate(nums2, 8);  // 8 % 4 = 0
        System.out.println("k кратна длине: " + Arrays.toString(nums2));
        
        // Edge case 4: Большой k
        int[] nums3 = {1, 2, 3, 4, 5};
        ArrayRotation.rotate(nums3, 1000002);  // 1000002 % 5 = 2
        System.out.println("Большой k: " + Arrays.toString(nums3));
    }
}

Сравнение подходов

Вывод для интервью

На интервью рекомендуется:

1. Сначала: решение "Три разворота" — оптимально по памяти и времени
2. Если задача: поворот «на месте» — это главное требование
3. Упомянуть: нормализация k = k % length для больших значений
4. Нарисовать: диаграмму трёх шагов разворота

Ключевые моменты:

• In-place решение требует O(1) память
• Нормализация k избегает излишних операций
• Метод разворота гениален по простоте и эффективности