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

Решение

Понимание задачи

Повернуть квадратную матрицу на 90 градусов по часовой стрелке.

Алгоритм: Транспонирование + Разворот

Оптимальный подход использует два этапа:

1. Транспонирование — строки становятся столбцами
2. Разворот каждой строки — каждая строка разворачивается

def rotate_matrix(matrix):
    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()
    return matrix

Пример выполнения

Матрица: [[1, 2], [3, 4]]

Шаг 1 - Транспонирование: [[1, 3], [2, 4]] Шаг 2 - Разворот строк: [[3, 1], [4, 2]]

Сложность

• Временная: O(n²) — посещаем каждый элемент дважды
• Пространственная: O(1) — модифицируем матрицу на месте

Тестирование

# Тест 1: 2x2 матрица
m = [[1, 2], [3, 4]]
rotate_matrix(m)
assert m == [[3, 1], [4, 2]]

# Тест 2: 3x3 матрица
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix(m)
assert m == [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

# Тест 3: 1x1 матрица
m = [[1]]
rotate_matrix(m)
assert m == [[1]]

Выводы

• Два этапа алгоритма просты для понимания
• O(n²) время и O(1) дополнительная память
• Работает для матриц любого размера
• Нужно тестировать на матрицах с чётными и нечётными размерами