Transpose Matrix

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

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

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

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

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

+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]: матрица 3 × 2.

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

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

Подсказки

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

Открыто 0 из 3

Решение

Транспонирование ничего не вычисляет: значение в (i, j) перемещается в (j, i). Меняется форма. В результате получается n строк длиной m, поэтому список строк, не являющийся квадратным, нельзя транспонировать на месте; создайте новую матрицу поменянного размера и заполните её.

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

Идея

Строка j ответа — это столбец j входных данных, прочитанный сверху вниз. Для [[1, 2, 3], [4, 5, 6]] в столбце 0 сначала идёт 1, затем 4, поэтому первая строка ответа — [1, 4].

Каждое значение считывается один раз и записывается один раз: время 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]. Это верно, потому что транспонирование — это именно такая перестановка индексов, выполненная один раз для каждой ячейки.

Каждое значение копируется один раз, поэтому время работы составляет 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

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

Создание результата с размерностями, как у входных данных. Для примера 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.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Аргумент

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

Ожидаемый вывод

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