Transpose Matrix

Q: Какова временная сложность транспонирования матрицы?

Это O(m × n) , потому что каждое из m × n значений копируется один раз, и ничто меньшее не может дать ответ. Новая матрица занимает O(m × n) памяти — столько же, сколько занимает сам результат.

Q: Можно ли транспонировать матрицу на месте?

Для квадратной матрицы — да: поменяйте местами matrix[i][j] и matrix[j][i] для каждой ячейки выше диагонали, используя дополнительную память O(1) . Для неквадратной матрицы результат будет иметь другую форму, поэтому при представлении в виде списка строк нужна новая матрица.

Q: Как транспонировать неквадратную матрицу?

Создай результат из n строк длиной m , где входная матрица состоит из m строк длиной n . Затем скопируй каждое значение с помощью result[j][i] = matrix[i][j] . Идея диагонали для квадратного случая здесь не применима, потому что матрицы имеют разную форму.

НовичокМассивы и строки

+10

Вам дана матрица целых чисел в виде списка строк: matrix[i][j] — это значение в строке i, столбце j. Верните её транспонированную матрицу — матрицу, которую получают, превращая каждую строку в столбец. Значение из строки i, столбца j перемещается в строку j, столбец i. Матрица не обязательно должна быть квадратной: матрица m × n становится матрицей n × m.

Функция

transpose(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: матрица m × n в виде списка из m строк, содержащих n целых чисел
Возвращаетinteger-2d-array: транспонированную матрицу n × m в виде списка из n строк по m целых чисел

Ограничения

1 ≤ m, n ≤ 1000, где m = matrix.length и n = matrix[i].length
m × n ≤ 5000
Каждая строка имеет одинаковую длину n.
-1000 ≤ matrix[i][j] ≤ 1000

Примеры

Ввод: matrix = [[1, 2, 3], [4, 5, 6]]
Вывод: [[1, 4], [2, 5], [3, 6]]
Пояснение: Первая строка [1, 2, 3] становится первым столбцом, а [4, 5, 6] — вторым. Если читать результат по строкам, получим [1, 4], [2, 5], [3, 6]: матрица 2 × 3 превратилась в матрицу 3 × 2.

+15 скрытых тестов при отправке

Дополнительный вопрос

Предположим, матрица хранится в виде одного плоского массива из m × n значений, строка за строкой. Можешь транспонировать неквадратную матрицу внутри этого массива, не используя второй массив?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Транспонирование — это простое изменение адреса: значение в (i, j) перемещается в (j, i), и ничего не вычисляется. Главное — правильно задать форму. Неквадратную матрицу, хранящуюся в виде списка строк, нельзя транспонировать на месте, потому что в результате будет n строк длины m вместо m строк длины n, поэтому нужно создать новую матрицу переставленного размера и заполнить её.

Читайте матрицу по одному столбцу за раз

Идея

Строка j в ответе — это столбец j входной матрицы, прочитанный сверху вниз. Поэтому формируй ответ по одной строке за раз: для каждого столбца j от 0 до n-1 собери matrix[0][j], matrix[1][j] и так далее до matrix[m-1][j], а затем добавь этот список как следующую строку.

Для [[1, 2, 3], [4, 5, 6]] в столбце 0 сначала читается 1, затем 4; в столбце 1 — 2, затем 5; в столбце 2 — 3, затем 6. Ответ: [[1, 4], [2, 5], [3, 6]], где n = 3 строки по m = 2 значения.

Каждое значение читается один раз и записывается один раз, поэтому временная сложность составляет O(m × n), а для результата требуется O(m × n) памяти. Затраты связаны с шаблоном доступа: при построении одной новой строки затрагивается каждая строка входной матрицы, переходя от строки к строке вместо последовательного чтения одной строки.

Алгоритм

Пусть m — количество строк, а n — длина строки.
Для каждого столбца j от 0 до n-1 создайте пустой список.
Добавьте в него matrix[i][j] для каждого i от 0 до m-1.
Добавьте список в результат как строку j и верните результат после последнего столбца.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Заполните новую сетку n × m, зеркально отразив каждую ячейку

Идея

Сначала определите форму, затем заполните её. В ответе n строк длины m, поэтому сначала создайте такую таблицу. Затем считывайте входные данные в их естественном порядке, строка за строкой и слева направо, и помещайте каждое значение по адресу с зеркально переставленными индексами: result[j][i] = matrix[i][j].

Это правило верно, потому что транспонирование — это именно перестановка двух индексов. В квадратном примере [[1, 2], [3, 4]] единица и четвёрка на диагонали остаются на своих местах, двойка перемещается из (0, 1) в (1, 0), а тройка — из (1, 0) в (0, 1), в результате получается [[1, 3], [2, 4]].

Каждое из m × n значений копируется один раз, поэтому временная сложность составляет O(m × n), а новая таблица занимает O(m × n) памяти, которая в любом случае необходима для выходных данных. Считывание входных данных по строкам позволяет обращаться к памяти в порядке хранения, а каждая строка результата создаётся один раз и сразу нужного размера.

Алгоритм

Пусть m — количество строк, а n — длина строки.
Создай result с n строками, в каждой из которых содержится m значений.
Для каждой строки i и каждого столбца j входной матрицы установи result[j][i] = matrix[i][j].
Верни result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Ловушки и крайние случаи

Почти каждый неправильный ответ связан с формой, а не со значениями.

Создание результата с исходной формой. Результат из m строк и n столбцов подходит только для квадратного входного массива; для примера 2 × 3 обращение к result[2][0] выходит за границы массива. Результат должен содержать n строк длины m.
Перестановка элементов на месте в неквадратной матрице. Перестановка matrix[i][j] и matrix[j][i] работает только при m = n, и даже тогда цикл должен охватывать только ячейки выше диагонали (j > i), иначе каждая пара будет переставлена дважды, и матрица вернётся к исходному виду.
Использование одного объекта строки для всех строк. В Python запись [[0] * m] * n создаёт n ссылок на один и тот же список, поэтому запись в одну ячейку изменяет весь столбец. Создавай каждую строку отдельно.
Забывание размеров столбцов в C. Вызывающий код считывает *returnSize как количество строк результата, n, а (*returnColumnSizes)[j] — как длину каждой строки, m.

Частые вопросы4

Что такое транспонирование матрицы?

Это матрица, которую вы получаете, меняя строки и столбцы местами: значение в строке i, столбце j перемещается в строку j, столбец i. Матрица 2 × 3 становится матрицей 3 × 2, а двойное транспонирование возвращает исходную матрицу.

Какова временная сложность транспонирования матрицы?

Это O(m × n), потому что каждое из m × n значений копируется один раз, и ничто меньшее не может дать ответ. Новая матрица занимает O(m × n) памяти — столько же, сколько занимает сам результат.

Можно ли транспонировать матрицу на месте?

Для квадратной матрицы — да: поменяйте местами matrix[i][j] и matrix[j][i] для каждой ячейки выше диагонали, используя дополнительную память O(1). Для неквадратной матрицы результат будет иметь другую форму, поэтому при представлении в виде списка строк нужна новая матрица.

Как транспонировать неквадратную матрицу?

Создай результат из n строк длиной m, где входная матрица состоит из m строк длиной n. Затем скопируй каждое значение с помощью result[j][i] = matrix[i][j]. Идея диагонали для квадратного случая здесь не применима, потому что матрицы имеют разную форму.

Python

def transpose(matrix):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

matrix = [[1, 2, 3], [4, 5, 6]]

Ожидается

[[1, 4], [2, 5], [3, 6]]