Rotate Image

Q: Qual é a complexidade de tempo e espaço para rotacionar uma matriz?

Girar uma matriz n × n leva tempo O(n²), já que quase todos os valores precisam ser movidos uma vez. O método de transpor e inverter precisa de espaço extra O(1). Construir uma cópia girada também leva tempo O(n²), mas usa espaço extra O(n²).

MédioArrays e strings Matemática e simulação

+10

Você recebe uma grade n × n de números inteiros, uma lista por linha. Gire-a um quarto de volta no sentido horário e retorne-a. A linha superior se torna a coluna mais à direita, a segunda linha se torna a coluna à esquerda dela, e assim por diante: o valor em (i, j) vai para (j, n-1-i). Você pode alterar a grade no próprio lugar; retorne-a.

Função

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

matrixinteger-2d-array: a grade quadrada, uma lista interna por linha
Retornainteger-2d-array: a matriz girou 90 graus no sentido horário

Restrições

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Exemplos

Entrada: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Saída: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Explicação: A primeira linha, 3 7 1, torna-se a última coluna, lida de cima para baixo. A primeira coluna, 3 9 4, lida de baixo para cima, torna-se a primeira linha [4, 9, 3]. O valor central 5 permanece no lugar.

Para ir além

Quais duas etapas in-place giram a matriz em 180 graus, e você consegue fazer isso em uma única passagem de trocas?

Dicas

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

0 de 3 abertas

Solução

O destino de cada valor segue uma fórmula: (i, j) vai para (j, n-1-i). A parte difícil é mover os valores sem uma segunda matriz, porque gravar um valor em sua nova célula sobrescreve outro que ainda não foi movido. Uma transposição seguida da inversão de uma linha produz o mesmo giro de um quarto de volta por meio de trocas em pares.

Crie uma cópia girada

Intuição

A linha i torna-se a coluna n-1-i, e o valor na posição j da linha vai para a posição j nessa coluna, que é a linha j. Então, result[j][n-1-i] = matrix[i][j]. No primeiro exemplo, o 4 na linha 2, coluna 0 vai para a linha 0, coluna 0, por isso a resposta começa com 4.

Os valores se movem em ciclos de quatro, então escrever no próprio lugar apagaria um valor antes que ele pudesse ser movido: o 3 sobrescreveria o 1 no canto superior direito. A cópia custa n² células extras, 4.900 para n = 70.

Algoritmo

Crie uma matriz de resultado n × n.
Para cada linha i e coluna j, copie matrix[i][j] para result[j][n-1-i].
Retorne o resultado.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transponha e, em seguida, inverta cada linha

Intuição

Uma transposição move (i, j) para (j, i), e inverter uma linha move a coluna c para a coluna n-1-c. Juntas, essas operações enviam (i, j) para (j, n-1-i), exatamente para onde a rotação o coloca.

Ambas as operações são executadas no próprio lugar, pois cada uma consiste em um conjunto de trocas entre pares. Em uma transposição, matrix[i][j] e matrix[j][i] pertencem, cada uma, à célula da outra, então uma troca conclui ambas. Troque apenas os pares com j > i, ou cada par será trocado de volta. Inverter uma linha troca suas duas extremidades e avança para o centro.

No primeiro exemplo, a transposição resulta em [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: cada linha agora contém uma antiga coluna. Inverter cada linha produz a resposta.

A transposição faz n(n-1)/2 trocas e as inversões fazem n·⌊n/2⌋, então o trabalho é O(n²), com algumas variáveis de memória extra. A versão em R primeiro copia a entrada para uma matriz R, então sua memória extra é O(n²).

Algoritmo

Para cada célula acima da diagonal principal, (i, j) com j > i, troque seu valor com o da célula (j, i).
Para cada linha, troque o primeiro e o último valor e avance pelas duas extremidades em direção ao centro até que se encontrem.
Retorne a matriz.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Armadilhas e casos extremos

Transpondo com j começando em 0. Cada par é trocado duas vezes, o que cancela a transposição; assim, o resultado são apenas as linhas invertidas, uma imagem espelhada.
Invertendo antes de transpor. Essa ordem gira a matriz no sentido anti-horário. Um teste 2 × 2 detecta isso: [[1, 2], [3, 4]] deve se tornar [[3, 1], [4, 2]].
Escrevendo matrix[j][n-1-i] = matrix[i][j] na mesma matriz. A célula de destino ainda contém um valor que não foi movido, e ele se perde.
Usando n-i em vez de n-1-i. Com índices começando em 0, a última coluna é n-1, então n-i ultrapassa o limite para i = 0.

Perguntas frequentes3

Qual é a complexidade de tempo e espaço para rotacionar uma matriz?

Girar uma matriz n × n leva tempo O(n²), já que quase todos os valores precisam ser movidos uma vez. O método de transpor e inverter precisa de espaço extra O(1). Construir uma cópia girada também leva tempo O(n²), mas usa espaço extra O(n²).

Como girar uma matriz no sentido anti-horário?

Troque a ordem das duas etapas: primeiro inverta cada linha e depois faça a transposição. Você também pode fazer a transposição e, em seguida, inverter a ordem das linhas. De qualquer forma, o valor em (i, j) termina em (n-1-j, i).

Você consegue girar uma matriz movendo quatro valores por vez?

Sim. Cada valor fora do centro pertence a um ciclo de quatro células: (i, j), (j, n-1-i), (n-1-i, n-1-j) e (n-1-j, i). Anel por anel, armazene um valor de cada ciclo em uma variável e desloque os outros três. Tem o mesmo tempo O(n²) e espaço O(1), com mais cálculos de índices para errar.

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

Teste #1

Teste #2

Argumento

matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]

Saída Esperada

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]