Dado un número n, imprima una array espiral xn (de números del 1 al nxn) en el sentido de las agujas del reloj utilizando el espacio O(1).
Ejemplo :
Input: n = 5 Output: 25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La solución se vuelve simple si se permite espacio adicional. Asignamos memoria para la array nxn y para cada elemento que comienza desde n*n hasta 1, comenzamos a completar la array en orden espiral. Para mantener el orden de la espiral, se utilizan cuatro bucles, cada uno para las esquinas superior, derecha, inferior e izquierda de la array.
Pero, ¿cómo resolverlo en el espacio O(1)?
Una array nxn tiene ceil(n/2) ciclos cuadrados. Un ciclo está formado por la i-ésima fila, (n-i+1)-ésima columna, (n-i+1)-ésima fila y la i-ésima columna donde i varía de 1 a ceil(n/2).
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17
- El primer ciclo está formado por elementos de su primera fila, última columna, última fila y primera columna (marcados por ). El primer ciclo consta de elementos de n*n a (n-2)*(n-2) + 1, es decir, de 25 a 10.
- El segundo ciclo está formado por elementos de segunda fila, penúltima columna, penúltima fila y segunda columna (marcados por ). El segundo ciclo consta de elementos de (n-2)*(n-2) a (n-4)*(n-4) + 1, es decir, de 9 a 2.
- El tercer ciclo está formado por elementos de tercera fila, penúltima columna, penúltima fila y tercera columna (marcados en negro ). El tercer ciclo consta de elementos de (n-4)*(n-4) a 1, es decir, solo 1.
La idea es que a cada ciclo cuadrado le asociemos un marcador. Para el ciclo exterior, el marcador tendrá el valor 0, para el segundo ciclo, tendrá el valor 1 y para el tercer ciclo tendrá el valor 2. En general, para una array xn, el i-ésimo ciclo tendrá el valor del marcador de i – 1.
Si divida la array en dos partes, el triángulo superior derecho (marcado por ) y el triángulo inferior izquierdo (marcado por ), luego usando el marcador x, podemos calcular fácilmente el valor que estará presente en el índice (i, j) en cualquier nxn array espiral usando la siguiente fórmula:
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17
For upper right half, mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x) For lower left half, mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)
A continuación se muestra la implementación de la idea.
C++
// C++ program to print a n x n spiral matrix
// in clockwise direction using O(1) space
#include <bits/stdc++.h>
using namespace std;
// Prints spiral matrix of size n x n containing
// numbers from 1 to n x n
void printSpiral(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// x stores the layer in which (i, j)th
// element lies
int x;
// Finds minimum of four inputs
x = min(min(i, j), min(n-1-i, n-1-j));
// For upper right half
if (i <= j)
printf("%d\t ", (n-2*x)*(n-2*x) - (i-x)
- (j-x));
// for lower left half
else
printf("%d\t ", (n-2*x-2)*(n-2*x-2) + (i-x)
+ (j-x));
}
printf("\n");
}
}
// Driver code
int main()
{
int n = 5;
// print a n x n spiral matrix in O(1) space
printSpiral(n);
return 0;
}
C
// C program to print a n x n spiral matrix
// in clockwise direction using O(1) space
#include <stdio.h>
// Prints spiral matrix of size n x n containing
// numbers from 1 to n x n
int min(int a,int b)
{
int min = a;
if(min > b)
min = b;
return min;
}
void printSpiral(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// x stores the layer in which (i, j)th
// element lies
int x;
// Finds minimum of four inputs
x = min(min(i, j), min(n-1-i, n-1-j));
// For upper right half
if (i <= j)
printf("%d\t ", (n-2*x)*(n-2*x) - (i-x)
- (j-x));
// for lower left half
else
printf("%d\t ", (n-2*x-2)*(n-2*x-2) + (i-x)
+ (j-x));
}
printf("\n");
}
}
// Driver code
int main()
{
int n = 5;
// print a n x n spiral matrix in O(1) space
printSpiral(n);
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to print a n x n spiral matrix
// in clockwise direction using O(1) space
import java.io.*;
import java.util.*;
class GFG {
// Prints spiral matrix of size n x n
// containing numbers from 1 to n x n
static void printSpiral(int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// x stores the layer in which (i, j)th
// element lies
int x;
// Finds minimum of four inputs
x = Math.min(Math.min(i, j),
Math.min(n - 1 - i, n - 1 - j));
// For upper right half
if (i <= j)
System.out.print((n - 2 * x) * (n - 2 * x) -
(i - x) - (j - x) + "\t");
// for lower left half
else
System.out.print((n - 2 * x - 2) * (n - 2 * x - 2) +
(i - x) + (j - x) + "\t");
}
System.out.println();
}
}
// Driver code
public static void main(String args[])
{
int n = 5;
// print a n x n spiral matrix in O(1) space
printSpiral(n);
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 program to print a n x n spiral matrix # in clockwise direction using O(1) space # Prints spiral matrix of size n x n # containing numbers from 1 to n x n def printSpiral(n) : for i in range(0, n) : for j in range(0, n) : # Finds minimum of four inputs x = min(min(i, j), min(n - 1 - i, n - 1 - j)) # For upper right half if (i <= j) : print((n - 2 * x) * (n - 2 * x) - (i - x)- (j - x), end = "\t") # For lower left half else : print(((n - 2 * x - 2) * (n - 2 * x - 2) + (i - x) + (j - x)), end = "\t") print() # Driver code n = 5 # print a n x n spiral matrix # in O(1) space printSpiral(n) # This code is contributed by Nikita Tiwari.
C#
// C# program to print a n x n
// spiral matrix in clockwise
// direction using O(1) space
using System;
class GFG {
// Prints spiral matrix of
// size n x n containing
// numbers from 1 to n x n
static void printSpiral(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// x stores the layer in which
// (i, j)th element lies
int x;
// Finds minimum of four inputs
x = Math.Min(Math.Min(i, j),
Math.Min(n - 1 - i, n - 1 - j));
// For upper right half
if (i <= j)
Console.Write((n - 2 * x) *
(n - 2 * x) -
(i - x) - (j - x) + "\t");
// for lower left half
else
Console.Write((n - 2 * x - 2) *
(n - 2 * x - 2) +
(i - x) + (j - x) + "\t");
}
Console.WriteLine();
}
}
// Driver code
public static void Main()
{
int n = 5;
// print a n x n spiral
// matrix in O(1) space
printSpiral(n);
}
}
// This code is contributed by KRV
PHP
<?php
// PHP program to print a n x n
// spiral matrix in clockwise
// direction using O(1) space
// Prints spiral matrix of size
// n x n containing numbers
// from 1 to n x n
function printSpiral($n)
{
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
// x stores the layer in
// which (i, j)th element lies
$x;
// Finds minimum of four inputs
$x = min(min($i, $j), min($n - 1 - $i,
$n - 1 - $j));
// For upper right half
if ($i <= $j)
echo "\t ", ($n - 2 * $x) *
($n - 2 * $x) -
($i - $x) - ($j - $x);
// for lower left half
else
echo "\t ", ($n - 2 * $x - 2) *
($n - 2 * $x - 2) +
($i - $x) + ($j - $x);
}
echo "\n";
}
}
// Driver code
$n = 5;
// print a n x n spiral
// matrix in O(1) space
printSpiral($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to print a
// n x n spiral matrix in clockwise
// direction using O(1) space
// Prints spiral matrix of size
// n x n containing numbers from
// 1 to n x n
function printSpiral(n)
{
for(let i = 0; i < n; i++)
{
for(let j = 0; j < n; j++)
{
// x stores the layer in which (i, j)th
// element lies
let x;
// Finds minimum of four inputs
x = Math.min(Math.min(i, j),
Math.min(n - 1 - i, n - 1 - j));
// For upper right half
if (i <= j)
document.write(`${(n - 2 * x) *
(n - 2 * x) -
(i - x) - (j - x)} `);
// For lower left half
else
document.write(`${(n - 2 * x - 2) *
(n - 2 * x - 2) +
(i - x) + (j - x)} `);
}
document.write("<br>");
}
}
// Driver code
let n = 5;
// Print a n x n spiral matrix in O(1) space
printSpiral(n);
// This code is contributed by subham348
</script>
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17
Complejidad temporal: O(n 2 ).
Espacio Auxiliar: O(1)
Ejercicio:
Para un número dado n, imprima una array espiral xn en dirección contraria a las manecillas del reloj usando el espacio O(1).
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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