Transpose Matrix

Q: Qual é a complexidade de tempo da transposição de uma matriz?

O(m × n) : cada um dos m × n valores é copiado uma vez, e nada menos que isso pode produzir a resposta. A nova matriz ocupa O(m × n) de espaço, o tamanho da própria saída.

Q: Você pode transpor uma matriz no próprio lugar?

Para uma matriz quadrada, sim: troque matrix[i][j] por matrix[j][i] para cada célula acima da diagonal, usando O(1) de memória extra. Uma matriz não quadrada muda de formato, então, com uma lista de linhas, você precisa de uma nova matriz.

InicianteArrays e strings

+10

Você recebe uma matriz de inteiros como uma lista de linhas: matrix[i][j] é o valor na linha i, coluna j. Retorne sua transposta: o valor na linha i, coluna j passa para a linha j, coluna i, de modo que cada linha se torne uma coluna. A matriz não precisa ser quadrada: uma matriz m × n se torna uma matriz n × m.

Função

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

matrixinteger-2d-array: a matriz m × n, como uma lista de m linhas de n números inteiros
Retornainteger-2d-array: a transposta n × m, como uma lista de n linhas de m inteiros

Restrições

1 ≤ m, n ≤ 1000, em que m = matrix.length e n = matrix[i].length
m × n ≤ 5000
Cada linha tem o mesmo comprimento n.
-1000 ≤ matrix[i][j] ≤ 1000

Exemplos

Entrada: matrix = [[1, 2, 3], [4, 5, 6]]
Saída: [[1, 4], [2, 5], [3, 6]]
Explicação: A linha [1, 2, 3] se torna a primeira coluna, e [4, 5, 6], a segunda. Lendo linha por linha, o resultado é [1, 4], [2, 5], [3, 6]: uma matriz 3 × 2.

Para ir além

Suponha que a matriz esteja armazenada em um único array linear com m × n valores, linha após linha. Você consegue transpor uma matriz não quadrada dentro desse array, sem usar um segundo array?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Transpor não calcula nada: o valor em (i, j) passa para (j, i). O trabalho está no formato. O resultado tem n linhas de comprimento m, então uma lista não quadrada de linhas não pode ser transposta no próprio lugar; crie uma nova matriz com as dimensões invertidas e preencha-a.

Leia a matriz uma coluna de cada vez

Intuição

A linha j da resposta é a coluna j da entrada, lida de cima para baixo. Para [[1, 2, 3], [4, 5, 6]], a coluna 0 lê 1 e depois 4, então a primeira linha da resposta é [1, 4].

Cada valor é lido uma vez e escrito uma vez: tempo O(m × n) e espaço O(m × n) para o resultado. Construir cada nova linha percorre todas as linhas da entrada em vez de ler ao longo de uma delas, que é a maneira mais lenta de percorrer a memória.

Algoritmo

Seja m o número de linhas e n o comprimento de uma linha.
Para cada coluna j, de 0 a n-1, comece com uma lista vazia.
Adicione matrix[i][j] a ela para cada i, de 0 a m-1.
Adicione a lista ao resultado como linha j e retorne o resultado após a última coluna.

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

Preencha uma nova grade n × m espelhando cada célula

Intuição

Crie o resultado n × m antecipadamente, depois leia a entrada na ordem em que está armazenada, linha por linha, e coloque cada valor em seu endereço espelhado: result[j][i] = matrix[i][j]. Isso está correto porque uma transposta é exatamente essa troca de índices, aplicada uma vez a cada célula.

Cada valor é copiado uma vez, então o tempo é O(m × n), e a grade ocupa o espaço O(m × n) de que a saída precisa de qualquer forma. A leitura por linhas percorre a memória na ordem em que está armazenada, e cada linha do resultado é alocada uma vez, já com seu tamanho final.

Algoritmo

Seja m o número de linhas e n o comprimento de uma linha.
Crie result com n linhas, cada uma contendo m valores.
Para cada linha i e cada coluna j da entrada, defina result[j][i] = matrix[i][j].
Retorne 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

Armadilhas e casos extremos

Construir o resultado com o mesmo formato da entrada. No exemplo 2 × 3, escrever result[2][0] ultrapassa o limite: o resultado precisa de n linhas com comprimento m.
Trocar matrix[i][j] por matrix[j][i] no próprio lugar. Isso só funciona quando m = n e apenas nas células com j > i; um loop por todas as células troca cada par duas vezes e retorna a matriz inalterada.
Em Python, [[0] * m] * n cria n referências à mesma lista, então escrever em uma célula altera uma coluna inteira. Crie cada linha separadamente.
Em C, quem chama lê *returnSize como o número de linhas do resultado, n, e (*returnColumnSizes)[j] como o comprimento de cada linha, m.

Perguntas frequentes3

O que é a transposta de uma matriz?

É a matriz que você obtém ao trocar linhas e colunas: o valor na linha i, coluna j passa para a linha j, coluna i. Uma matriz 2 × 3 se torna 3 × 2, e transpor duas vezes retorna à matriz original.

Qual é a complexidade de tempo da transposição de uma matriz?

O(m × n): cada um dos m × n valores é copiado uma vez, e nada menos que isso pode produzir a resposta. A nova matriz ocupa O(m × n) de espaço, o tamanho da própria saída.

Você pode transpor uma matriz no próprio lugar?

Para uma matriz quadrada, sim: troque matrix[i][j] por matrix[j][i] para cada célula acima da diagonal, usando O(1) de memória extra. Uma matriz não quadrada muda de formato, então, com uma lista de linhas, você precisa de uma nova matriz.

def transpose(matrix):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

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

Saída Esperada

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