Поворот матрицы на 90 градусов

Поворот матрицы на 90 градусов

Это классическая задача с ограничением на дополнительную память (in-place). Существуют несколько подходов разной сложности.

1. Анализ проблемы

При повороте на 90 градусов по часовой стрелке:

• Первая строка становится последним столбцом
• Первый столбец становится первой строкой (в обратном порядке)

Исходная матрица:    После поворота на 90°:
1 2 3                7 4 1
4 5 6      →         8 5 2
7 8 9                9 6 3

Преобразование:
Element[i][j] → Element[j][n-1-i]

2. Простое решение — дополнительный массив

def rotate_simple(matrix: list[list[int]]) -> None:
    """Поворот с использованием дополнительной матрицы."""
    n = len(matrix)
    rotated = [[0] * n for _ in range(n)]
    
    # Копируем элементы в новую матрицу с поворотом
    for i in range(n):
        for j in range(n):
            rotated[j][n - 1 - i] = matrix[i][j]
    
    # Копируем обратно
    for i in range(n):
        for j in range(n):
            matrix[i][j] = rotated[i][j]

# Тестирование
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_simple(matrix)
print(matrix)  # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Анализ:

• Время: O(n²) — посещаем каждый элемент один раз
• Память: O(n²) — дополнительная матрица
• Проблема: НЕ in-place

3. Оптимальное решение — слой за слоем (In-Place)

def rotate_inplace(matrix: list[list[int]]) -> None:
    """Поворот матрицы на 90 градусов без дополнительной памяти."""
    n = len(matrix)
    
    # Обрабатываем слои матрицы снаружи внутрь
    for layer in range(n // 2):
        first = layer
        last = n - 1 - layer
        
        for i in range(first, last):
            offset = i - first
            
            # Сохраняем верхний элемент
            top = matrix[first][i]
            
            # Левый → верхний
            matrix[first][i] = matrix[last - offset][first]
            
            # Нижний → левый
            matrix[last - offset][first] = matrix[last][last - offset]
            
            # Правый → нижний
            matrix[last][last - offset] = matrix[i][last]
            
            # Верхний → правый
            matrix[i][last] = top

# Тестирование
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_inplace(matrix)
print(matrix)  # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Визуализация для 3×3 матрицы:

Шаг 1: layer=0 (внешний слой)
       first=0, last=2

Обработка 4-х углов в цикле:
i=0: offset=0
    Сохраняем: top = matrix[0][0] = 1
    matrix[0][0] = matrix[2][0] = 7  (левый → верхний)
    matrix[2][0] = matrix[2][2] = 9  (нижний → левый)
    matrix[2][2] = matrix[0][2] = 3  (правый → нижний)
    matrix[0][2] = top = 1            (верхний → правый)
    
    Матрица:
    7 2 1
    4 5 6
    9 8 3

i=1: offset=1
    Сохраняем: top = matrix[0][1] = 2
    matrix[0][1] = matrix[1][0] = 4  (левый → верхний)
    matrix[1][0] = matrix[2][1] = 8  (нижний → левый)
    matrix[2][1] = matrix[1][2] = 6  (правый → нижний)
    matrix[1][2] = top = 2            (верхний → правый)
    
    Матрица:
    7 4 1
    8 5 2
    9 6 3

Шаг 2: layer=1 (внутренний слой)
       first=1, last=1
       Цикл не выполняется (first >= last)

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

Анализ:

• Время: O(n²) — посещаем каждый элемент один раз
• Память: O(1) — только несколько переменных
• In-Place: ✓ Используем исходный массив

4. Альтернатива — транспонирование + зеркало

def rotate_transpose(matrix: list[list[int]]) -> None:
    """Поворот через транспонирование и отражение."""
    n = len(matrix)
    
    # Шаг 1: Транспонирование
    # matrix[i][j] → matrix[j][i]
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Шаг 2: Зеркальное отражение каждой строки
    # matrix[i][j] → matrix[i][n-1-j]
    for i in range(n):
        matrix[i].reverse()

# Тестирование
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_transpose(matrix)
print(matrix)  # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Визуализация:

Шаг 1: Транспонирование
1 2 3       1 4 7
4 5 6  →    2 5 8
7 8 9       3 6 9

Шаг 2: Зеркальное отражение строк
1 4 7       7 4 1
2 5 8  →    8 5 2
3 6 9       9 6 3

Анализ:

• Время: O(n²)
• Память: O(1)
• Преимущество: Более интуитивный код

5. Полная реализация с тестами

from typing import List
import unittest

class Solution:
    @staticmethod
    def rotate(matrix: List[List[int]]) -> None:
        """Оптимальное решение: слой за слоем."""
        n = len(matrix)
        
        for layer in range(n // 2):
            first = layer
            last = n - 1 - layer
            
            for i in range(first, last):
                offset = i - first
                
                top = matrix[first][i]
                matrix[first][i] = matrix[last - offset][first]
                matrix[last - offset][first] = matrix[last][last - offset]
                matrix[last][last - offset] = matrix[i][last]
                matrix[i][last] = top
    
    @staticmethod
    def rotate_transpose(matrix: List[List[int]]) -> None:
        """Альтернатива: транспонирование + отражение."""
        n = len(matrix)
        
        # Транспонирование
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # Зеркальное отражение
        for i in range(n):
            matrix[i].reverse()


class TestRotateMatrix(unittest.TestCase):
    
    def test_3x3_matrix(self):
        """Стандартный пример 3×3."""
        matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
        expected = [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
        Solution.rotate(matrix)
        self.assertEqual(matrix, expected)
    
    def test_2x2_matrix(self):
        """Матрица 2×2."""
        matrix = [[1, 2], [3, 4]]
        expected = [[3, 1], [4, 2]]
        Solution.rotate(matrix)
        self.assertEqual(matrix, expected)
    
    def test_1x1_matrix(self):
        """Матрица 1×1."""
        matrix = [[1]]
        expected = [[1]]
        Solution.rotate(matrix)
        self.assertEqual(matrix, expected)
    
    def test_4x4_matrix(self):
        """Матрица 4×4."""
        matrix = [
            [1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]
        ]
        expected = [
            [13, 9, 5, 1],
            [14, 10, 6, 2],
            [15, 11, 7, 3],
            [16, 12, 8, 4]
        ]
        Solution.rotate(matrix)
        self.assertEqual(matrix, expected)
    
    def test_transpose_method(self):
        """Проверяем альтернативный метод."""
        matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
        expected = [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
        Solution.rotate_transpose(matrix)
        self.assertEqual(matrix, expected)

if __name__ == '__main__':
    unittest.main()

6. Сравнение методов

7. Граничные случаи

def test_edge_cases():
    # 1x1 матрица
    matrix = [[1]]
    Solution.rotate(matrix)
    assert matrix == [[1]]
    
    # 2x2 матрица (нечётная размерность дважды)
    matrix = [[1, 2], [3, 4]]
    Solution.rotate(matrix)
    assert matrix == [[3, 1], [4, 2]]
    
    # Матрица с нулями
    matrix = [[0, 0], [0, 0]]
    Solution.rotate(matrix)
    assert matrix == [[0, 0], [0, 0]]
    
    # Матрица с отрицательными числами
    matrix = [[-1, -2], [-3, -4]]
    Solution.rotate(matrix)
    assert matrix == [[-3, -1], [-4, -2]]

8. Поворот на другие углы

def rotate_90(matrix):
    """Поворот на 90 градусов."""
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for i in range(n):
        matrix[i].reverse()

def rotate_180(matrix):
    """Поворот на 180 градусов."""
    rotate_90(matrix)
    rotate_90(matrix)

def rotate_270(matrix):
    """Поворот на 270 градусов."""
    rotate_90(matrix)
    rotate_90(matrix)
    rotate_90(matrix)

def rotate_counterclockwise(matrix):
    """Поворот против часовой стрелки (270 градусов)."""
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Вывод

Для поворота матрицы на 90 градусов:

1. Оптимальное решение: Транспонирование + зеркальное отражение (O(1) память)
2. Альтернатива: Слой за слоем (циклический поворот элементов)
3. Ключевое понимание: Element[i][j] → Element[j][n-1-i]
4. In-Place: Оба метода работают без дополнительной памяти
5. Практическое применение: Обработка изображений, игры, графика

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