Dada una array cuadrada, gírela 90 grados en sentido contrario a las agujas del reloj sin usar ningún espacio adicional.
Ejemplos:
Input: Matrix: 1 2 3 4 5 6 7 8 9 Output: 3 6 9 2 5 8 1 4 7 The given matrix is rotated by 90 degree in anti-clockwise direction. Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 The given matrix is rotated by 90 degree in anti-clockwise direction.
Aquí ya se analiza un enfoque que requiere espacio adicional .
Planteamiento: Para resolver la pregunta sin ningún espacio adicional, gire la array en forma de cuadrados, dividiendo la array en cuadrados o ciclos. Por ejemplo,
una array de 4 X 4 tendrá 2 ciclos. El primer ciclo está formado por su 1ª fila, última columna, última fila y 1ª columna. El segundo ciclo está formado por 2ª fila, penúltima columna, penúltima fila y 2ª columna. La idea es para cada ciclo cuadrado, intercambiar los elementos involucrados con la celda correspondiente en la array en sentido contrario a las agujas del reloj, es decir, de arriba a izquierda, de izquierda a abajo, de abajo a la derecha y de derecha a arriba, uno a la vez usando nada más que un variable temporal para lograrlo.
Demostración:
First Cycle (Involves Red Elements) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Moving first group of four elements (First elements of 1st row, last row, 1st column and last column) of first cycle in counter clockwise. 4 2 3 16 5 6 7 8 9 10 11 12 1 14 15 13 Moving next group of four elements of first cycle in counter clockwise 4 8 3 16 5 6 7 15 2 10 11 12 1 14 9 13 Moving final group of four elements of first cycle in counter clockwise 4 8 12 16 3 6 7 15 2 10 11 14 1 5 9 13 Second Cycle (Involves Blue Elements) 4 8 12 16 3 6 7 15 2 10 11 14 1 5 9 13 Fixing second cycle 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
Algoritmo:
- Hay N/2 cuadrados o ciclos en una array de lado N. Procesa un cuadrado a la vez. Ejecute un ciclo para atravesar la array un ciclo a la vez, es decir, un ciclo de 0 a N/2 – 1, el contador de ciclo es i
- Considere los elementos en un grupo de 4 en el cuadro actual, gire los 4 elementos a la vez. Entonces, el número de tales grupos en un ciclo es N – 2*i.
- Así que ejecute un ciclo en cada ciclo de x a N – x – 1, el contador de ciclo es y
- Los elementos en el grupo actual son (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), ahora gire el estos 4 elementos, es decir (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N- 1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
- Imprime la array.
Implementación:
C++
// C++ program to rotate a matrix
// by 90 degrees
#include <bits/stdc++.h>
#define N 4
using namespace std;
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
void rotateMatrix(int mat[][N])
{
// Consider all squares one by one
for (int x = 0; x < N / 2; x++) {
// Consider elements in group
// of 4 in current square
for (int y = x; y < N - x - 1; y++) {
// Store current cell in
// temp variable
int temp = mat[x][y];
// Move values from right to top
mat[x][y] = mat[y][N - 1 - x];
// Move values from bottom to right
mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y];
// Move values from left to bottom
mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x];
// Assign temp to left
mat[N - 1 - y][x] = temp;
}
}
}
// Function to print the matrix
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
/* Driver program to test above functions */
int main()
{
// Test Case 1
int mat[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[N][N] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[N][N] = {
{1, 2},
{4, 5}
};*/
// displayMatrix(mat);
rotateMatrix(mat);
// Print rotated matrix
displayMatrix(mat);
return 0;
}
Java
// Java program to rotate a
// matrix by 90 degrees
import java.io.*;
class GFG {
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
static void rotateMatrix(int N, int mat[][])
{
// Consider all squares one by one
for (int x = 0; x < N / 2; x++) {
// Consider elements in group
// of 4 in current square
for (int y = x; y < N - x - 1; y++) {
// Store current cell in
// temp variable
int temp = mat[x][y];
// Move values from right to top
mat[x][y] = mat[y][N - 1 - x];
// Move values from bottom to right
mat[y][N - 1 - x]
= mat[N - 1 - x][N - 1 - y];
// Move values from left to bottom
mat[N - 1 - x][N - 1 - y]
= mat[N - 1 - y][x];
// Assign temp to left
mat[N - 1 - y][x] = temp;
}
}
}
// Function to print the matrix
static void displayMatrix(int N, int mat[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + mat[i][j]);
System.out.print("\n");
}
System.out.print("\n");
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int N = 4;
// Test Case 1
int mat[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[][] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[][] = {
{1, 2},
{4, 5}
};*/
// displayMatrix(mat);
rotateMatrix(N, mat);
// Print rotated matrix
displayMatrix(N, mat);
}
}
// This code is contributed by Prakriti Gupta
Python3
# Python3 program to rotate a matrix by 90 degrees
N = 4
# An Inplace function to rotate
# N x N matrix by 90 degrees in
# anti-clockwise direction
def rotateMatrix(mat):
# Consider all squares one by one
for x in range(0, int(N / 2)):
# Consider elements in group
# of 4 in current square
for y in range(x, N-x-1):
# store current cell in temp variable
temp = mat[x][y]
# move values from right to top
mat[x][y] = mat[y][N-1-x]
# move values from bottom to right
mat[y][N-1-x] = mat[N-1-x][N-1-y]
# move values from left to bottom
mat[N-1-x][N-1-y] = mat[N-1-y][x]
# assign temp to left
mat[N-1-y][x] = temp
# Function to print the matrix
def displayMatrix(mat):
for i in range(0, N):
for j in range(0, N):
print(mat[i][j], end=' ')
print("")
# Driver Code
mat = [[0 for x in range(N)] for y in range(N)]
# Test case 1
mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
'''
# Test case 2
mat = [ [1, 2, 3 ],
[4, 5, 6 ],
[7, 8, 9 ] ]
# Test case 3
mat = [ [1, 2 ],
[4, 5 ] ]
'''
rotateMatrix(mat)
# Print rotated matrix
displayMatrix(mat)
# This code is contributed by saloni1297
C#
// C# program to rotate a
// matrix by 90 degrees
using System;
class GFG {
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in anti-
// clockwise direction
static void rotateMatrix(int N, int[, ] mat)
{
// Consider all
// squares one by one
for (int x = 0; x < N / 2; x++) {
// Consider elements
// in group of 4 in
// current square
for (int y = x; y < N - x - 1; y++) {
// store current cell
// in temp variable
int temp = mat[x, y];
// move values from
// right to top
mat[x, y] = mat[y, N - 1 - x];
// move values from
// bottom to right
mat[y, N - 1 - x]
= mat[N - 1 - x, N - 1 - y];
// move values from
// left to bottom
mat[N - 1 - x, N - 1 - y]
= mat[N - 1 - y, x];
// assign temp to left
mat[N - 1 - y, x] = temp;
}
}
}
// Function to print the matrix
static void displayMatrix(int N, int[, ] mat)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
Console.Write(" " + mat[i, j]);
Console.WriteLine();
}
Console.WriteLine();
}
// Driver Code
static public void Main()
{
int N = 4;
// Test Case 1
int[, ] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[][] =
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[][] =
{
{1, 2},
{4, 5}
};*/
// displayMatrix(mat);
rotateMatrix(N, mat);
// Print rotated matrix
displayMatrix(N, mat);
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to rotate a
// matrix by 90 degrees
$N = 4;
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
function rotateMatrix(&$mat)
{
global $N;
// Consider all
// squares one by one
for ($x = 0; $x < $N / 2; $x++)
{
// Consider elements
// in group of 4 in
// current square
for ($y = $x;
$y < $N - $x - 1; $y++)
{
// store current cell
// in temp variable
$temp = $mat[$x][$y];
// move values from
// right to top
$mat[$x][$y] = $mat[$y][$N - 1 - $x];
// move values from
// bottom to right
$mat[$y][$N - 1 - $x] =
$mat[$N - 1 - $x][$N - 1 - $y];
// move values from
// left to bottom
$mat[$N - 1 - $x][$N - 1 - $y] =
$mat[$N - 1 - $y][$x];
// assign temp to left
$mat[$N - 1 - $y][$x] = $temp;
}
}
}
// Function to
// print the matrix
function displayMatrix(&$mat)
{
global $N;
for ($i = 0; $i < $N; $i++)
{
for ($j = 0; $j < $N; $j++)
echo $mat[$i][$j] . " ";
echo "\n";
}
echo "\n";
}
// Driver code
// Test Case 1
$mat = array(array(1, 2, 3, 4),
array(5, 6, 7, 8),
array(9, 10, 11, 12),
array(13, 14, 15, 16));
// Test Case 2
/* $mat = array(array(1, 2, 3),
array(4, 5, 6),
array(7, 8, 9));
*/
// Test Case 3
/*$mat = array(array(1, 2),
array(4, 5));*/
// displayMatrix($mat);
rotateMatrix($mat);
// Print rotated matrix
displayMatrix($mat);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to rotate a
// matrix by 90 degrees
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
function rotateMatrix(N,mat)
{
// Consider all squares one by one
for (let x = 0; x < N / 2; x++)
{
// Consider elements in group
// of 4 in current square
for (let y = x; y < N - x - 1; y++)
{
// Store current cell in
// temp variable
let temp = mat[x][y];
// Move values from right to top
mat[x][y] = mat[y][N - 1 - x];
// Move values from bottom to right
mat[y][N - 1 - x]
= mat[N - 1 - x][N - 1 - y];
// Move values from left to bottom
mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x];
// Assign temp to left
mat[N - 1 - y][x] = temp;
}
}
}
// Function to print the matrix
function displayMatrix(N,mat)
{
for (let i = 0; i < N; i++)
{
for (let j = 0; j < N; j++)
document.write(
" " + mat[i][j]);
document.write("<br>");
}
document.write("<br>");
}
/* Driver program to test above functions */
let N = 4;
let mat=[[1, 2, 3, 4],[ 5, 6, 7, 8 ],[9, 10, 11, 12 ],[13, 14, 15, 16]];
// displayMatrix(mat);
rotateMatrix(N, mat);
// Print rotated matrix
displayMatrix(N, mat);
// This code is contributed by rag2127.
</script>
Producción
4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
Análisis de Complejidad:
- Complejidad de tiempo: O(n 2 ), donde n es el lado de la array.
Se necesita un solo recorrido de la array. - Complejidad espacial: O(1).
Como se necesita un espacio constante
Fácil de entender y aplicar
Otro enfoque:
- Invertir cada fila individual
- Realizar transposición
Implementación:
C++
// C++ program to rotate a matrix
// by 90 degrees
#include <bits/stdc++.h>
#define N 4
using namespace std;
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
void rotateMatrix(int mat[][N])
{ // REVERSE every row
for (int i = 0; i < N; i++)
reverse(mat[i], mat[i] + N);
// Performing Transpose
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++)
swap(mat[i][j], mat[j][i]);
}
}
// Function to print the matrix
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/* Driver program to test above functions */
int main()
{
// Test Case 1
int mat[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[N][N] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[N][N] = {
{1, 2},
{4, 5}
};*/
// displayMatrix(mat);
rotateMatrix(mat);
// Print rotated matrix
displayMatrix(mat);
return 0;
}
Java
// Java program to rotate a
// matrix by 90 degrees
import java.io.*;
class GFG {
// Function to reverse
// the given 2D arr[][]
static void Reverse(int i,int mat[][], int N)
{
// Initialise start and end index
int start = 0;
int end = N - 1;
// Till start < end, swap the element
// at start and end index
while (start < end) {
// Swap the element
int temp = mat[i][start];
mat[i][start] = mat[i][end];
mat[i][end] = temp;
// Increment start and decrement
// end for next pair of swapping
start++;
end--;
}
}
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
static void rotateMatrix(int N, int mat[][])
{ // REVERSE every row
for (int i = 0; i < N; i++)
Reverse(i,mat,N);
// Performing Transpose
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++)
{
int temp=mat[i][j];
mat[i][j]=mat[j][i];
mat[j][i]=temp;
}
}
}
// Function to print the matrix
static void displayMatrix(int N, int mat[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + mat[i][j]);
System.out.print("\n");
}
System.out.print("\n");
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int N = 4;
// Test Case 1
int mat[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
rotateMatrix(N, mat);
// Print rotated matrix
displayMatrix(N, mat);
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python program to rotate # a matrix by 90 degrees def rotateMatrix(mat): # reversing the matrix for i in range(len(mat)): mat[i].reverse() # make transpose of the matrix for i in range(len(mat)): for j in range(i, len(mat)): # swapping mat[i][j] and mat[j][i] mat[i][j], mat[j][i] = mat[j][i], mat[i][j] # Function to print the matrix def displayMatrix(mat): for i in range(0, len(mat)): for j in range(0, len(mat)): print(mat[i][j], end=' ') print() mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] rotateMatrix(mat) # Print rotated matrix displayMatrix(mat) # This code is contributed by shivambhagat02(CC).
C#
// C# program to rotate a
// matrix by 90 degrees
using System;
class GFG {
// Reverse each row of matrix
static void reverse(int N, int[, ] mat)
{
// Traverse each row of [,]mat
for (int i = 0; i < N; i++) {
// Initialise start and end index
int start = 0;
int end = N - 1;
// Till start < end, swap the element
// at start and end index
while (start < end) {
// Swap the element
int temp = mat[i,start];
mat[i, start] = mat[i, end];
mat[i, end] = temp;
// Increment start and decrement
// end for next pair of swapping
start++;
end--;
}
}
}
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in anti-
// clockwise direction
static void rotateMatrix(int N, int[, ] mat)
{
reverse(N, mat);
// Performing Transpose
for(int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
int temp = mat[i,j];
mat[i, j] = mat[j, i];
mat[j, i] = temp;
}
}
}
// Function to print the matrix
static void displayMatrix(int N, int[, ] mat)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
Console.Write(mat[i, j] + " ");
Console.Write("\n");
}
}
// Driver Code
static public void Main()
{
int N = 4;
// Test Case 1
int[, ] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[][] =
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[][] =
{
{1, 2},
{4, 5}
};*/
// displayMatrix(mat);
rotateMatrix(N, mat);
// Print rotated matrix
displayMatrix(N, mat);
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript program to rotate
// a matrix by 90 degrees
function rotateMatrix(mat){
// reversing the matrix
for(let i = 0; i < mat.length; i++){
mat[i].reverse()
}
// make transpose of the matrix
for(let i = 0; i < mat.length; i++){
for(let j = i; j < mat.length; j++){
// swapping mat[i][j] and mat[j][i]
let temp = mat[i][j]
mat[i][j] = mat[j][i]
mat[j][i] = temp
}
}
}
// Function to print the matrix
function displayMatrix(mat){
for(let i = 0; i < mat.length; i++){
for(let j = 0; j < mat.length; j++){
document.write(mat[i][j],' ')
}
document.write("</br>")
}
}
let mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
rotateMatrix(mat)
// Print rotated matrix
displayMatrix(mat)
// This code is contributed by shinjanpatra
</script>
Producción
4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
Análisis de Complejidad:
- Complejidad de tiempo: O(n 2 ) + O(n 2 ) donde n es el tamaño de la array.
- Espacio Auxiliar: O(1) . Como se necesita un espacio constante
Ejercicio: gire la array 2D 90 grados en el sentido de las agujas del reloj sin usar espacio adicional.
Gire una array 90 grados sin usar ningún espacio adicional | conjunto 2
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA