Dada una array rectangular mat[][] con N filas y M columnas, la tarea es rotar la array 90 grados en el sentido de las agujas del reloj sin usar espacio adicional.
Ejemplos:
Entrada: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}
Salida: 10 7 4 1
11 8 5 2
12 9 6 3Entrada: mat[][] = {{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}}
Salida: 7 1
8 2
9 3
10 4
11 5
12 6
Nota: El enfoque para rotar una array cuadrada ya se analiza de la siguiente manera:
- Con espacio adicional: Inplace rotar la array cuadrada 90 grados | Serie 1
- Sin espacio adicional en sentido contrario a las agujas del reloj: gira una array 90 grados sin usar espacio adicional | conjunto 2
Enfoque: La idea principal es realizar una rotación en el lugar.
Siga los pasos a continuación para resolver el problema dado:
- Intercambie todos los elementos de la subarray min(N, M) * min(N, M) , a lo largo de la diagonal principal, es decir, desde la esquina superior superior hasta la esquina inferior derecha.
- Si N es mayor que M ,
- Empuje todos los elementos no intercambiados de cada columna i donde (min(N, M) ≤ i) a la i -ésima fila.
- De lo contrario, empuje todos los elementos no intercambiados de cada fila i donde (min(N, M) ≤ i) a la i -ésima columna.
- Invertir cada fila de la array
- Imprime la array actualizada de dimensión M × N .
Procedimiento:
Sea la array dada:
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
Intercambie todos los elementos de la subarray min(N, M) * min(N, M) es decir, 3 * 3 para este ejemplo
1 4 7
2 5 8
3 6 9
10 11 12
13 14 15
Como N > M, empuje todos los elementos no intercambiados de cada columna i (min(N, M) ≤ i) a la i -ésima fila
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15
Invierta cada columna para obtener la array rotada final como:
13 10 7 4 1
14 11 8 5 2
15 12 9 6 3
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the matrix mat
// with N rows and M columns
void print(vector<vector<int> > mat,
int N, int M)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << mat[i][j] << " ";
}
cout << "\n";
}
}
// Function to rotate the matrix
// by 90 degree clockwise
void rotate(vector<vector<int> > mat)
{
// Number of rows
int N = mat.size();
// Number of columns
int M = mat[0].size();
// Swap all the elements along main diagonal
// in the submatrix min(N, M) * min(N, M)
for (int i = 0; i < min(N, M); i++) {
for (int j = i; j < min(N, M); j++) {
// Swap mat[i][j] and mat[j][i]
swap(mat[i][j], mat[j][i]);
}
}
// If N is greater than M
if (N > M) {
// Push all the unswapped elements
// of ith column to ith row
for (int i = 0; i < M; i++) {
for (int j = min(N, M); j < N; j++) {
mat[i].push_back(mat[j][i]);
}
}
}
else {
// Resize mat to have M rows
mat.resize(M, {});
// Push all the unswapped elements
// of ith column to ith row
for (int i = min(N, M); i < M; i++) {
for (int j = 0; j < N; j++) {
mat[i].push_back(mat[j][i]);
}
}
}
// Reverse each row of the matrix
for (int i = 0; i < M; i++) {
reverse(mat[i].begin(), mat[i].end());
}
// Print the final matrix
print(mat, M, N);
}
// Driver Code
int main()
{
// Input
vector<vector<int> > mat = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 },
{ 10, 11, 12 } };
// Function Call
rotate(mat);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Java program for
// the above approach
// Function to print the matrix mat
// with N rows and M columns
static void print(ArrayList<ArrayList<Integer>> mat,int N, int M)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(mat.get(i).get(j) + " ");
}
System.out.println();
}
}
// Function to rotate the matrix
// by 90 degree clockwise
static void rotate(ArrayList<ArrayList<Integer>> mat)
{
// Number of rows
int N = mat.size();
// Number of columns
int M = mat.get(0).size();
// Swap all the elements along main diagonal
// in the submatrix min(N, M) * min(N, M)
for (int i = 0; i < Math.min(N, M); i++) {
for (int j = i; j < Math.min(N, M); j++) {
// Swap mat[i][j] and mat[j][i]
int temp = mat.get(i).get(j);
mat.get(i).set(j,mat.get(j).get(i));
mat.get(j).set(i,temp);
}
}
// If N is greater than M
if (N > M) {
// Push all the unswapped elements
// of ith column to ith row
for (int i = 0; i < M; i++) {
for (int j = Math.min(N, M); j < N; j++) {
mat.get(i).add(mat.get(j).get(i));
}
}
}
else {
// Resize mat to have M rows
mat = new ArrayList<>(M);
for(int i=0;i<M;i++){
mat.add(i , new ArrayList<>());
}
// Push all the unswapped elements
// of ith column to ith row
for (int i = Math.min(N, M); i < M; i++) {
for (int j = 0; j < N; j++) {
mat.get(i).add(mat.get(j).get(i));
}
}
}
// Reverse each row of the matrix
for (int i = 0; i < M; i++) {
Collections.reverse(mat.get(i));
}
// Print the final matrix
print(mat, M, N);
}
/* Driver program to test above function*/
public static void main(String args[])
{
// Input
ArrayList<ArrayList<Integer>> mat = new ArrayList<>();
mat.add(new ArrayList<Integer>(Arrays.asList(1,2,3)));
mat.add(new ArrayList<Integer>(Arrays.asList(4,5,6)));
mat.add(new ArrayList<Integer>(Arrays.asList(7,8,9)));
mat.add(new ArrayList<Integer>(Arrays.asList(10,11,12)));
// Function Call
rotate(mat);
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program for # the above approach # Function to print the matrix mat # with N rows and M columns def Print(mat, N, M): for i in range(N): for j in range(M): print(mat[i][j] , end = " ") print() # Function to rotate the matrix # by 90 degree clockwise def rotate(mat): # Number of rows N = len(mat) # Number of columns M = len(mat[0]) # Swap all the elements along main diagonal # in the submatrix min(N, M) * min(N, M) for i in range(min(N, M)): for j in range(i,min(N, M)): # Swap mat[i][j] and mat[j][i] mat[i][j], mat[j][i] = mat[j][i], mat[i][j] # If N is greater than M if (N > M): # Push all the unswapped elements # of ith column to ith row for i in range(M): for j in range(min(N, M),N): mat[i].append(mat[j][i]) else: # Resize mat to have M rows mat = [[] for i in range(M)] # Push all the unswapped elements # of ith column to ith row for i in range(min(N, M),M): for j in range(N): mat[i].append(mat[j][i]) # Reverse each row of the matrix for i in range(M): mat[i] = mat[i][::-1] # Print the final matrix Print(mat, M, N) # Driver Code # Input mat = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ], [ 10, 11, 12 ] ] # Function Call rotate(mat) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program for
// the above approach
// Function to print the matrix mat
// with N rows and M columns
function print(mat,N,M)
{
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
document.write(mat[i][j] , " ");
}
document.write("</br>");
}
}
// Function to rotate the matrix
// by 90 degree clockwise
function rotate(mat)
{
// Number of rows
let N = mat.length;
// Number of columns
let M = mat[0].length;
// Swap all the elements along main diagonal
// in the submatrix min(N, M) * min(N, M)
for (let i = 0; i < Math.min(N, M); i++) {
for (let j = i; j < Math.min(N, M); j++) {
// Swap mat[i][j] and mat[j][i]
let temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
// If N is greater than M
if (N > M) {
// Push all the unswapped elements
// of ith column to ith row
for (let i = 0; i < M; i++) {
for (let j = Math.min(N, M); j < N; j++) {
mat[i].push(mat[j][i]);
}
}
}
else {
// Resize mat to have M rows
mat = new Array(M).fill(0).map(()=>[])
// Push all the unswapped elements
// of ith column to ith row
for (let i = Math.min(N, M); i < M; i++) {
for (let j = 0; j < N; j++) {
mat[i].push(mat[j][i]);
}
}
}
// Reverse each row of the matrix
for (let i = 0; i < M; i++) {
mat[i] = mat[i].reverse();
}
// Print the final matrix
print(mat, M, N);
}
// Driver Code
// Input
let mat = [ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ],
[ 10, 11, 12 ] ];
// Function Call
rotate(mat);
// This code is contributed by shinjanpatra
</script>
Producción
10 7 4 1 11 8 5 2 12 9 6 3
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)