Como você gira uma matriz bidimensional?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Inspirado por Postagem de Raymond Chen, digamos que você tenha uma matriz bidimensional 4x4, escreva uma função que a gire 90 graus.Raymond vincula-se a uma solução em pseudocódigo, mas eu gostaria de ver algumas coisas do mundo real.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
Torna-se:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
Atualizar:A resposta de Nick é a mais direta, mas existe uma maneira de fazer isso melhor do que n^2?E se a matriz fosse 10.000x10.000?
Solução
Aqui está em C#
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
Outras dicas
Algoritmo O (n ^ 2) de tempo e O (1) espaço (sem soluções alternativas e coisas complicadas!)
Girar em +90:
- Transpor
- Inverta cada linha
Girar em -90:
Método 1 :
- Transpor
- Inverter cada coluna
Método 2:
- Inverta cada linha
- Transpor
Girar em +180:
Método 1:Gire +90 duas vezes
Método 2:Inverta cada linha e depois inverta cada coluna (Transpor)
Girar em -180:
Método 1:Gire em -90 duas vezes
Método 2:Inverta cada coluna e depois inverta cada linha
Método 3:Gire em +180, pois eles são iguais
Eu gostaria de adicionar um pouco mais de detalhes.Nesta resposta, os conceitos-chave são repetidos, o ritmo é lento e intencionalmente repetitivo.A solução aqui apresentada não é a mais compacta sintaticamente, mas destina-se a quem deseja aprender o que é rotação de matrizes e a implementação resultante.
Em primeiro lugar, o que é uma matriz?Para os fins desta resposta, uma matriz é apenas uma grade onde a largura e a altura são iguais.Observe que a largura e a altura de uma matriz podem ser diferentes, mas para simplificar, este tutorial considera apenas matrizes com largura e altura iguais (matrizes quadradas).E sim, matrizes é o plural de matriz.
Matrizes de exemplo são:2×2, 3×3 ou 5×5.Ou, mais geralmente, N×N.Uma matriz 2×2 terá 4 quadrados porque 2×2=4.Uma matriz 5×5 terá 25 quadrados porque 5×5=25.Cada quadrado é chamado de elemento ou entrada.Representaremos cada elemento com um ponto final (.) nos diagramas abaixo:
Matriz 2×2
. .
. .
Matriz 3×3
. . .
. . .
. . .
Matriz 4×4
. . . .
. . . .
. . . .
. . . .
Então, o que significa girar uma matriz?Vamos pegar uma matriz 2×2 e colocar alguns números em cada elemento para que a rotação possa ser observada:
0 1
2 3
Girar isso em 90 graus nos dá:
2 0
3 1
Literalmente viramos toda a matriz uma vez para a direita, como se girássemos o volante de um carro.Pode ser útil pensar em “inclinar” a matriz para o lado direito.Queremos escrever uma função, em Python, que pegue uma matriz e gire uma vez para a direita.A assinatura da função será:
def rotate(matrix):
# Algorithm goes here.
A matriz será definida usando uma matriz bidimensional:
matrix = [
[0,1],
[2,3]
]
Portanto, a primeira posição do índice acessa a linha.A segunda posição do índice acessa a coluna:
matrix[row][column]
Definiremos uma função de utilidade para imprimir uma matriz.
def print_matrix(matrix):
for row in matrix:
print row
Um método de girar uma matriz é fazer uma camada de cada vez.Mas o que é uma camada?Pense em uma cebola.Assim como as camadas de uma cebola, à medida que cada camada é removida, avançamos em direção ao centro.Outras analogias são Boneca matryoshka ou um jogo de passar o pacote.
A largura e a altura de uma matriz determinam o número de camadas dessa matriz.Vamos usar símbolos diferentes para cada camada:
Uma matriz 2×2 tem 1 camada
. .
. .
Uma matriz 3×3 tem 2 camadas
. . .
. x .
. . .
Uma matriz 4×4 tem 2 camadas
. . . .
. x x .
. x x .
. . . .
Uma matriz 5×5 tem 3 camadas
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Uma matriz 6×6 tem 3 camadas
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
Uma matriz 7×7 tem 4 camadas
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
Você pode notar que aumentar a largura e a altura de uma matriz em um nem sempre aumenta o número de camadas.Tomando as matrizes acima e tabulando as camadas e dimensões, vemos que o número de camadas aumenta uma vez para cada dois incrementos de largura e altura:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
No entanto, nem todas as camadas precisam de rotação.Uma matriz 1×1 é a mesma antes e depois da rotação.A camada central 1×1 é sempre a mesma antes e depois da rotação, não importa quão grande seja a matriz geral:
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
Dada a matriz N×N, como podemos determinar programaticamente o número de camadas que precisamos para girar?Se dividirmos a largura ou a altura por dois e ignorarmos o restante, obteremos os seguintes resultados.
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
Note como N/2 corresponde ao número de camadas que precisam ser giradas?Às vezes, o número de camadas rotativas é um a menos que o número total de camadas na matriz.Isto ocorre quando a camada mais interna é formada por apenas um elemento (ou seja,uma matriz 1×1) e, portanto, não precisa ser girada.Simplesmente é ignorado.
Sem dúvida precisaremos dessa informação em nossa função para rotacionar uma matriz, então vamos adicioná-la agora:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Agora que sabemos o que são camadas e como determinar o número de camadas que realmente precisam ser rotacionadas, como isolamos uma única camada para que possamos girá-la?Primeiramente, inspecionamos uma matriz desde a camada mais externa, para dentro, até a camada mais interna.Uma matriz 5×5 tem três camadas no total e duas camadas que precisam ser rotacionadas:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Vejamos primeiro as colunas.A posição das colunas que definem a camada mais externa, assumindo que contamos a partir de 0, são 0 e 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 e 4 também são as posições das linhas da camada mais externa.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Este será sempre o caso, pois a largura e a altura são iguais.Portanto, podemos definir as posições das colunas e linhas de uma camada com apenas dois valores (em vez de quatro).
Movendo-se para dentro da segunda camada, as posições das colunas são 1 e 3.E, sim, você adivinhou, é o mesmo para linhas.É importante entender que tivemos que aumentar e diminuir as posições das linhas e colunas ao avançar para a próxima camada.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
Portanto, para inspecionar cada camada, queremos um loop com contadores crescentes e decrescentes que representem o movimento para dentro, começando pela camada mais externa.Chamaremos isso de nosso ‘loop de camada’.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
O código acima percorre as posições (linha e coluna) de quaisquer camadas que precisam ser rotacionadas.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Agora temos um loop que fornece as posições das linhas e colunas de cada camada.As variáveis first e last identificar a posição do índice da primeira e da última linha e coluna.Referindo-nos às nossas tabelas de linhas e colunas:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Assim podemos navegar pelas camadas de uma matriz.Agora precisamos de uma forma de navegar dentro de uma camada para que possamos mover elementos em torno dessa camada.Observe que os elementos nunca “saltam” de uma camada para outra, mas se movem dentro de suas respectivas camadas.
Girar cada elemento em uma camada gira toda a camada.Girar todas as camadas em uma matriz gira toda a matriz.Esta frase é muito importante, então tente entendê-la ao máximo antes de prosseguir.
Agora, precisamos de uma maneira de realmente mover os elementos, ou seja,gire cada elemento e, posteriormente, a camada e, finalmente, a matriz.Para simplificar, reverteremos para uma matriz 3x3 — que possui uma camada rotativa.
0 1 2
3 4 5
6 7 8
Nosso loop de camada fornece os índices da primeira e da última coluna, bem como da primeira e da última linha:
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
Como nossas matrizes são sempre quadradas, precisamos apenas de duas variáveis, first e last, já que as posições do índice são iguais para linhas e colunas.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
As variáveis first e last podem ser facilmente usadas para fazer referência aos quatro cantos de uma matriz.Isso ocorre porque os próprios cantos podem ser definidos usando várias permutações de first e last (sem subtração, adição ou deslocamento dessas variáveis):
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
Por esse motivo, iniciamos nossa rotação nos quatro cantos externos — vamos girá-los primeiro.Vamos destacá-los com *.
* 1 *
3 4 5
* 7 *
Queremos trocar cada * com o * à direita dele.Então, vamos imprimir nossos cantos definidos usando apenas várias permutações de first e last:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
A saída deve ser:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Agora poderíamos facilmente trocar cada um dos cantos de nosso loop de camadas:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
Matriz antes de girar cantos:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Matriz após girar cantos:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Ótimo!Giramos com sucesso cada canto da matriz.Porém, não giramos os elementos no meio de cada camada.Claramente precisamos de uma maneira de iterar dentro de uma camada.
O problema é que o único loop em nossa função até agora (nosso loop de camada) passa para a próxima camada em cada iteração.Como nossa matriz possui apenas uma camada rotativa, o loop da camada sai após girar apenas os cantos.Vejamos o que acontece com uma matriz 5×5 maior (onde duas camadas precisam ser rotacionadas).O código da função foi omitido, mas permanece o mesmo acima:
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
A saída é:
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
Não deve ser uma surpresa que os cantos da camada mais externa tenham sido girados, mas você também pode notar que os cantos da próxima camada (para dentro) também foram girados.Isso faz sentido.Escrevemos código para navegar pelas camadas e também para girar os cantos de cada camada.Isto parece um progresso, mas infelizmente temos de dar um passo atrás.Não adianta passar para a próxima camada até que a camada anterior (externa) tenha sido totalmente girada.Isto é, até que cada elemento da camada tenha sido girado.Girar apenas os cantos não adianta!
Respire fundo.Precisamos de outro loop.Nada menos que um loop aninhado.O novo loop aninhado usará o first e last variáveis, além de um deslocamento para navegar dentro de uma camada.Chamaremos esse novo loop de ‘loop de elemento’.O loop de elementos visitará cada elemento ao longo da linha superior, cada elemento no lado direito, cada elemento ao longo da linha inferior e cada elemento no lado esquerdo.
- Avançar ao longo da linha superior exige que o índice da coluna seja incrementado.
- Descer o lado direito exige que o índice da linha seja incrementado.
- Mover para trás ao longo da parte inferior exige que o índice da coluna seja diminuído.
- Aumentar o lado esquerdo exige que o índice da linha seja diminuído.
Isto parece complexo, mas é fácil porque o número de vezes que aumentamos e diminuímos para alcançar o resultado acima permanece o mesmo em todos os quatro lados da matriz.Por exemplo:
- Mova 1 elemento na linha superior.
- Mova 1 elemento para baixo no lado direito.
- Mova 1 elemento para trás ao longo da linha inferior.
- Mova 1 elemento para cima no lado esquerdo.
Isso significa que podemos usar uma única variável em combinação com o first e last variáveis para mover dentro de uma camada.Pode ser útil observar que mover-se pela linha superior e para baixo no lado direito requer incrementos.Ao mover-se para trás ao longo da parte inferior e para cima no lado esquerdo, ambos exigem diminuição.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
Agora só precisamos atribuir o topo ao lado direito, o lado direito ao fundo, o fundo ao lado esquerdo e o lado esquerdo ao topo.Juntando tudo isso obtemos:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
Dada a matriz:
0, 1, 2
3, 4, 5
6, 7, 8
Nosso rotate função resulta em:
6, 3, 0
7, 4, 1
8, 5, 2
Pitão:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
Barato, eu sei.
E no sentido anti-horário:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Como isso funciona: (Solicitado nos comentários)
zip(*original) trocará eixos de matrizes 2D empilhando itens correspondentes de listas em novas listas.(O * operador diz à função para distribuir as listas contidas em argumentos)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
O [::-1] instrução inverte elementos do array (por favor veja Fatias Estendidas).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
Finalmente, combinar os dois resultará na transformação de rotação.
A mudança na colocação de [::-1] inverterá listas em diferentes níveis da matriz.
Aqui está um que faz a rotação no lugar, em vez de usar um array completamente novo para armazenar o resultado.Parei a inicialização do array e a imprimi.Isso funciona apenas para matrizes quadradas, mas elas podem ser de qualquer tamanho.A sobrecarga de memória é igual ao tamanho de um elemento do array, então você pode fazer a rotação de um array tão grande quanto desejar.
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
Há muitos códigos bons aqui, mas eu só quero mostrar o que está acontecendo geometricamente para que você possa entender um pouco melhor a lógica do código.Aqui está como eu abordaria isso.
antes de mais nada, não confunda isso com transposição que é muito fácil.
a idéia básica é tratá-la como camadas e girar uma camada por vez.
digamos que temos um 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
depois de girarmos 90 no sentido horário, obtemos
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
então vamos decompor isso, primeiro giramos os 4 cantos essencialmente
1 4
13 16
então giramos o seguinte diamante que está meio torto
2
8
9
15
e então o segundo diamante distorcido
3
5
12
14
então isso cuida da borda externa, então essencialmente fazemos uma casca de cada vez até
finalmente o quadrado do meio (ou se for estranho apenas o elemento final que não se move)
6 7
10 11
então agora vamos descobrir os índices de cada camada, suponha que sempre trabalhamos com a camada mais externa, estamos fazendo
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
assim por diante e assim por diante até estarmos no meio da borda
então, em geral, o padrão é
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
Como eu disse em meu post anterior, aqui está um código em C# que implementa uma rotação de matriz O(1) para matrizes de qualquer tamanho.Por questões de brevidade e legibilidade, não há verificação de erros ou verificação de intervalo.O código:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
OK, vou levantar a mão, na verdade ele não faz nenhuma modificação no array original ao girar.Mas, em um sistema OO, isso não importa, desde que o objeto pareça ter sido rotacionado para os clientes da classe.No momento, a classe Matrix usa referências aos dados originais do array, portanto, alterar qualquer valor de m1 também alterará m2 e m3.Uma pequena alteração no construtor para criar um novo array e copiar os valores para ele resolverá isso.
Embora a rotação dos dados no local possa ser necessária (talvez para atualizar a representação armazenada fisicamente), torna-se mais simples e possivelmente mais eficiente adicionar uma camada de indireção ao acesso ao array, talvez uma interface:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Se seu Matrix já implementa esta interface, então ela pode ser rotacionada através de um decorador classe assim:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
Girar +90/-90/180 graus, inverter horizontalmente/verticalmente e dimensionar também podem ser alcançados desta forma.
O desempenho precisaria ser medido em seu cenário específico.No entanto, a operação O(n^2) foi agora substituída por uma chamada O(1).É uma chamada de método virtual que é mais lento que o acesso direto ao array, portanto depende da frequência com que o array girado é usado após a rotação.Se for usado uma vez, essa abordagem definitivamente venceria.Se for girado e usado em um sistema de longa duração por dias, a rotação no local poderá funcionar melhor.Também depende se você pode aceitar o custo inicial.
Tal como acontece com todas as questões de desempenho, meça, meça, meça!
Esta é uma versão melhor em Java:Eu fiz isso para uma matriz com largura e altura diferentes
- h é aqui a altura da matriz após girar
- w é aqui a largura da matriz após girar
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
Este código é baseado na postagem de Nick Berardi.
Caminho Ruby: .transpose.map &:reverse
Já existem muitas respostas e encontrei duas alegando complexidade de tempo O(1).O real O algoritmo O(1) deve deixar o armazenamento do array intacto e alterar a forma como você indexa seus elementos.O objetivo aqui é que ele não consuma memória adicional nem exija tempo adicional para iterar os dados.
Rotações de 90, -90 e 180 graus são transformações simples que podem ser realizadas desde que você saiba quantas linhas e colunas existem em seu array 2D;Para girar qualquer vetor em 90 graus, troque os eixos e negue o eixo Y.Para -90 graus, troque os eixos e negue o eixo X.Para 180 graus, negue ambos os eixos sem trocar.
Outras transformações são possíveis, como espelhamento horizontal e/ou vertical negando os eixos independentemente.
Isto pode ser feito através, e.um método acessador.Os exemplos abaixo são funções JavaScript, mas os conceitos se aplicam igualmente a todas as linguagens.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);Este código assume uma matriz de matrizes aninhadas, onde cada matriz interna é uma linha.
O método permite ler (ou escrever) elementos (mesmo em ordem aleatória) como se o array tivesse sido girado ou transformado.Agora basta escolher a função certa para chamar, provavelmente por referência, e pronto!
O conceito pode ser estendido para aplicar transformações de forma aditiva (e não destrutiva) através dos métodos acessadores.Incluindo rotações e escalas de ângulos arbitrários.
Algumas pessoas já colocaram exemplos que envolvem a criação de um novo array.
Algumas outras coisas a considerar:
(a) Em vez de realmente mover os dados, simplesmente percorra a matriz "girada" de maneira diferente.
(b) Fazer a rotação no local pode ser um pouco mais complicado.Você precisará de um pouco de espaço (provavelmente igual ao tamanho de uma linha ou coluna).Há um artigo antigo do ACM sobre como fazer transposições no local (http://doi.acm.org/10.1145/355719.355729), mas seu código de exemplo é um FORTRAN desagradável e carregado de goto.
Termo aditivo:
http://doi.acm.org/10.1145/355611.355612 é outro algoritmo de transposição local supostamente superior.
de Nick A resposta também funcionaria para um array NxM com apenas uma pequena modificação (em oposição a um NxN).
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
Uma maneira de pensar sobre isso é mover o centro do eixo (0,0) do canto superior esquerdo para o canto superior direito.Você está simplesmente transpondo de um para o outro.
Tempo - O(N), Espaço - O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
Aqui está minha versão Ruby (observe que os valores não são exibidos da mesma forma, mas ainda gira conforme descrito).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
A saída:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
aqui está um método de rotação no espaço, por java, apenas para quadrado.para array 2d não quadrado, você terá que criar um novo array de qualquer maneira.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
código para girar array 2d de qualquer tamanho criando um novo array:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
Implementação do pseudocódigo +90 do dimple (por exemplotransponha e inverta cada linha) em JavaScript:
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
Você pode fazer isso em 3 etapas fáceis:
1)Suponha que temos uma matriz
1 2 3
4 5 6
7 8 9
2) Faça a transposta da matriz
1 4 7
2 5 8
3 6 9
3) Troque linhas para obter a matriz girada
3 6 9
2 5 8
1 4 7
Java Código fonte por esta:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
Saída:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
Esta é a minha implementação, em C, complexidade de memória O(1), rotação no local, 90 graus no sentido horário:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
Aqui está a versão Java:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
o método primeiro gira a camada mais externa e depois passa para a camada interna sequencialmente.
Do ponto de vista linear, considere as matrizes:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
Agora faça uma transposição
1 4 7
A' = 2 5 8
3 6 9
E considere a ação de A' sobre B, ou de B sobre A'.
Respectivamente:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
Isso é expansível para qualquer matriz n x n.E aplicando esse conceito rapidamente no código:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
Código C# para girar matrizes 2D [n,m] 90 graus para a direita
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
Resultado:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X é o tamanho do array em que o gráfico está.
#transpose é um método padrão da classe Array do Ruby, portanto:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
A implementação é uma função de transposição n^2 escrita em C.Você pode vê-lo aqui:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transposeescolhendo "clique para alternar a fonte" ao lado de "transpor".
Lembro-me melhor do que soluções O (n ^ 2), mas apenas para matrizes especialmente construídas (como matrizes esparsas)
Código C para rotação da matriz 90 graus no sentido horário IN LOCAL para qualquer matriz M*N
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
aqui está minha implementação In Place em C
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
Aqui está minha tentativa de rotação de 90 graus da matriz, que é uma solução de 2 etapas em C.Primeiro transponha a matriz no lugar e depois troque as colunas.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@dagorym:Aw, meu.Eu estava pensando nisso como um bom quebra-cabeça do tipo "Estou entediado, o que posso pensar".Eu criei meu código de transposição local, mas cheguei aqui e descobri que o seu é praticamente idêntico ao meu... ah, bem.Aqui está em Ruby.
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
Método C++ simples, embora houvesse uma grande sobrecarga de memória em uma grande matriz.
