Transpose Matrix

Q: Qual é a complexidade de tempo de transpor uma matriz?

É O(m × n) , porque 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, que corresponde ao tamanho da própria saída.

Q: Você consegue 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 memória extra O(1) . Para uma matriz não quadrada, o resultado tem um formato diferente, então, com uma lista de linhas, você precisa de uma nova matriz.

Q: Como transpor uma matriz não quadrada?

Crie um resultado com n linhas de comprimento m , enquanto a entrada tem m linhas de comprimento n . Em seguida, copie cada valor com result[j][i] = matrix[i][j] . A ideia da diagonal do caso quadrado não se aplica, porque as duas matrizes não têm o mesmo formato.

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, a matriz obtida ao transformar cada linha em uma coluna. O valor na linha i, coluna j passa para a linha j, coluna i. 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 inteiros
Retornainteger-2d-array: a transposta de n × m, como uma lista de n linhas de m números inteiros

Restrições

1 ≤ m, n ≤ 1000, em que m = matrix.length e n = matrix[i].length
m × n ≤ 5000
Todas as linhas têm 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 primeira linha [1, 2, 3] se torna a primeira coluna, e [4, 5, 6], a segunda. Lendo o resultado linha por linha, obtemos [1, 4], [2, 5], [3, 6]: a matriz 2 × 3 se transformou em uma matriz 3 × 2.

+15 testes ocultos ao enviar

Para ir além

Suponha que a matriz esteja armazenada como um único array linear de 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 é apenas uma mudança de posição: o valor em (i, j) passa para (j, i), e nada é calculado. O trabalho é acertar o formato. Uma matriz não quadrada armazenada como uma lista de linhas não pode ser transposta no próprio lugar, porque o resultado tem n linhas de comprimento m, em vez de m linhas de comprimento n; portanto, você cria uma nova matriz com as dimensões invertidas e a preenche.

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. Então, construa a resposta uma linha por vez: para cada coluna j de 0 a n-1, colete matrix[0][j], matrix[1][j] e assim por diante até matrix[m-1][j], e adicione essa lista como a próxima linha.

Para [[1, 2, 3], [4, 5, 6]], a coluna 0 contém 1 e depois 4, a coluna 1 contém 2 e depois 5, a coluna 2 contém 3 e depois 6. A resposta é [[1, 4], [2, 5], [3, 6]], com n = 3 linhas de m = 2 valores.

Cada valor é lido uma vez e escrito uma vez, então o tempo é O(m × n) e o resultado ocupa O(m × n) espaço. O custo está no padrão de acesso: construir uma nova linha toca todas as linhas da entrada, saltando de uma linha para outra em vez de ler ao longo de uma só.

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 a 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

Decida primeiro o formato e, depois, preencha-o. A resposta tem n linhas de comprimento m, então crie essa grade logo de início. Em seguida, leia a entrada na ordem natural, linha por linha e da esquerda para a direita, e coloque cada valor em seu endereço espelhado: result[j][i] = matrix[i][j].

A regra está correta porque transpor é exatamente trocar os dois índices. No exemplo quadrado [[1, 2], [3, 4]], os valores 1 e 4 da diagonal permanecem onde estavam, 2 vai de (0, 1) para (1, 0), e 3 vai de (1, 0) para (0, 1), resultando em [[1, 3], [2, 4]].

Cada um dos m × n valores é copiado uma vez, então o tempo é O(m × n), e a nova grade ocupa o espaço O(m × n) de que a saída precisa de qualquer forma. Ler a entrada linha por linha percorre a memória na ordem em que está armazenada, e cada linha do resultado é criada uma única vez em 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

Quase todas as respostas incorretas se devem ao formato, não aos valores.

Construir o resultado com o formato original. Um resultado com m linhas e n colunas só funciona para uma entrada quadrada; no exemplo 2 × 3, escrever result[2][0] ultrapassa os limites. O resultado precisa de n linhas com comprimento m.
Trocar elementos no próprio lugar em uma matriz não quadrada. Trocar matrix[i][j] por matrix[j][i] só funciona quando m = n e, mesmo assim, o loop deve cobrir apenas as células acima da diagonal (j > i), ou cada par será trocado duas vezes e a matriz voltará ao estado original.
Compartilhar um único objeto de linha. Em Python, [[0] * m] * n cria n referências à mesma lista, então escrever em uma célula altera a coluna inteira. Crie cada linha separadamente.
Esquecer os tamanhos das colunas em C. O chamador lê *returnSize como o número de linhas do resultado, n, e (*returnColumnSizes)[j] como o comprimento de cada linha, m.

Perguntas frequentes4

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 resulta na matriz original.

Qual é a complexidade de tempo de transpor uma matriz?

É O(m × n), porque 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, que corresponde ao tamanho da própria saída.

Você consegue 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 memória extra O(1). Para uma matriz não quadrada, o resultado tem um formato diferente, então, com uma lista de linhas, você precisa de uma nova matriz.

Como transpor uma matriz não quadrada?

Crie um resultado com n linhas de comprimento m, enquanto a entrada tem m linhas de comprimento n. Em seguida, copie cada valor com result[j][i] = matrix[i][j]. A ideia da diagonal do caso quadrado não se aplica, porque as duas matrizes não têm o mesmo formato.

Python

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

Casos de teste

Caso 1

Caso 2

Entrada

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

Esperado

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