Dada una array, la tarea es convertir la array dada en una array espiral ordenada .
Ejemplos:
Input: y[][] = {
{ 2, 5, 12 },
{ 22, 54, 55 },
{ 1, 6, 8 }
};
Output:
1 2 5
45 55 6
22 12 8
Input: y[][] = {
{ 2, 5, 12 },
{ 22, 45, 55 },
{ 1, 6, 8 },
{ 13, 56, 10 }
};
Output:
1 2 5
45 55 6
22 56 8
13 12 10
Acercarse:
- Convierta la array 2D dada en una array 1D.
- Ordenar la array 1D
- Convertir 1D a array espiral
- Esto se puede resolver con 4 bucles for que almacenan todos los elementos. Cada bucle for define un movimiento de una sola dirección junto con la array. El primer ciclo for representa el movimiento de izquierda a derecha, mientras que el segundo rastreo representa el movimiento de arriba a abajo, el tercero representa el movimiento de derecha a izquierda y el cuarto representa el movimiento de abajo hacia arriba.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Convert given Matrix
// into sorted Spiral Matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Function to convert the array to Spiral
void ToSpiral(int m, int n,
int Sorted[], int a[MAX][MAX])
{
// For Array pointer
int index = 0;
// k - starting row index
// m - ending row index
// l - starting column index
// n - ending column index
int k = 0, l = 0;
while (k < m && l < n)
{
// Print the first row
// from the remaining rows
for (int i = l; i < n; ++i)
{
a[k][i] = Sorted[index];
index++;
}
k++;
// Print the last column
// from the remaining columns
for (int i = k; i < m; ++i)
{
a[i][n - 1] = Sorted[index];
index++;
}
n--;
// Print the last row
// from the remaining rows
if (k < m)
{
for (int i = n - 1; i >= l; --i)
{
a[m - 1][i] = Sorted[index];
index++;
}
m--;
}
// Print the first column
// from the remaining columns
if (l < n)
{
for (int i = m - 1; i >= k; --i)
{
a[i][l] = Sorted[index];
index++;
}
l++;
}
}
}
// Function to convert 2D array to 1D array
void convert2Dto1D(int y[MAX][MAX],
int m, int n,int x[])
{
int index = 0;
// Store value 2D Matrix To 1D array
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
x[index] = y[i][j];
index++;
}
}
}
// Function to print the Matrix
void PrintMatrix(int a[MAX][MAX],
int m, int n)
{
// Print Spiral Matrix
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
}
// Function to Convert given Matrix
// into sorted Spiral Matrix
void convertMatrixToSortedSpiral(
int y[MAX][MAX], int m, int n)
{
int a[MAX][MAX] = {0};
int x[m * n];
convert2Dto1D(y, m, n,x);
sort(x, x + n * m);
ToSpiral(m, n, x, a);
PrintMatrix(a, m, n);
}
// Driver code
int main()
{
int m = 4, n = 3;
int y[MAX][MAX] = {
{ 2, 5, 12 },
{ 22, 45, 55 },
{ 1, 6, 8 },
{ 13, 56, 10 }};
convertMatrixToSortedSpiral(y, m, n);
return 0;
}
// This code is contributed by Arnab Kundu
Java
// Java program to Convert given Matrix
// into sorted Spiral Matrix
import java.util.*;
public class TwistedMatrix {
static int MAX = 1000;
// Function to convert the array to Spiral
static void ToSpiral(int m, int n,
int Sorted[], int a[][])
{
// For Array pointer
int index = 0;
// k - starting row index
// m - ending row index
// l - starting column index
// n - ending column index
int k = 0, l = 0;
while (k < m && l < n) {
// Print the first row
// from the remaining rows
for (int i = l; i < n; ++i) {
a[k][i] = Sorted[index];
index++;
}
k++;
// Print the last column
// from the remaining columns
for (int i = k; i < m; ++i) {
a[i][n - 1] = Sorted[index];
index++;
}
n--;
// Print the last row
// from the remaining rows
if (k < m) {
for (int i = n - 1; i >= l; --i) {
a[m - 1][i] = Sorted[index];
index++;
}
m--;
}
// Print the first column
// from the remaining columns
if (l < n) {
for (int i = m - 1; i >= k; --i) {
a[i][l] = Sorted[index];
index++;
}
l++;
}
}
}
// Function to convert 2D array to 1D array
public static int[] convert2Dto1D(
int y[][], int m, int n)
{
int index = 0;
int x[] = new int[m * n];
// Store value 2D Matrix To 1D array
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
x[index] = y[i][j];
index++;
}
}
return x;
}
// Function to print the Matrix
public static void PrintMatrix(
int a[][], int m, int n)
{
// Print Spiral Matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
// Function to sort the array
public static int[] SortArray(int x[])
{
// Sort array Using InBuilt Function
Arrays.sort(x);
return x;
}
// Function to Convert given Matrix
// into sorted Spiral Matrix
public static void convertMatrixToSortedSpiral(
int y[][], int m, int n)
{
int a[][] = new int[MAX][MAX];
int x[] = new int[m * n];
x = convert2Dto1D(y, m, n);
x = SortArray(x);
ToSpiral(m, n, x, a);
PrintMatrix(a, m, n);
}
// Driver code
public static void main(String[] args)
{
int m = 4, n = 3;
int y[][] = {
{ 2, 5, 12 },
{ 22, 45, 55 },
{ 1, 6, 8 },
{ 13, 56, 10 }
};
convertMatrixToSortedSpiral(y, m, n);
}
}
// This article is contributed by VRUND R PATEL
Python 3
# Python3 program to Convert given Matrix
# into sorted Spiral Matrix
MAX = 1000
# Function to convert the array to Spiral
def ToSpiral(m, n, Sorted, a):
# For Array pointer
index = 0
# k - starting row index
# m - ending row index
# l - starting column index
# n - ending column index
k = 0
l = 0
while (k < m and l < n):
# Print the first row
# from the remaining rows
for i in range(l, n, 1):
a[k][i] = Sorted[index]
index += 1
k += 1
# Print the last column
# from the remaining columns
for i in range(k, m, 1):
a[i][n - 1] = Sorted[index]
index += 1
n -= 1
# Print the last row
# from the remaining rows
if (k < m):
i = n - 1
while(i >= l):
a[m - 1][i] = Sorted[index]
index += 1
i -= 1
m -= 1
# Print the first column
# from the remaining columns
if (l < n):
i = m - 1
while(i >= k):
a[i][l] = Sorted[index]
index += 1
i -= 1
l += 1
# Function to convert 2D array to 1D array
def convert2Dto1D(y, m, n):
index = 0
x = [0 for i in range(m * n)]
# Store value 2D Matrix To 1D array
for i in range(m):
for j in range(n):
x[index] = y[i][j]
index += 1
return x
# Function to print the Matrix
def PrintMatrix(a, m, n):
# Print Spiral Matrix
for i in range(m):
for j in range(n):
print(a[i][j], end =" ")
print('\n', end = "")
# Function to sort the array
def SortArray(x):
# Sort array Using InBuilt Function
x.sort(reverse = False)
return x
# Function to Convert given Matrix
# into sorted Spiral Matrix
def convertMatrixToSortedSpiral(y, m, n):
a = [[0 for i in range(MAX)]
for j in range(MAX)]
x = [0 for i in range(15)]
x = convert2Dto1D(y, m, n)
x = SortArray(x)
ToSpiral(m, n, x, a)
PrintMatrix(a, m, n)
# Driver code
if __name__ == '__main__':
m = 4
n = 3
y = [[2, 5, 12], [22, 45, 55],
[1, 6, 8], [13, 56, 10]]
convertMatrixToSortedSpiral(y, m, n)
# This code is contributed by Surendra_Gangwar
C#
// C# program to Convert given Matrix
// into sorted Spiral Matrix
using System;
class GFG
{
static int MAX = 1000;
// Function to convert the array to Spiral
static void ToSpiral(int m, int n,
int []Sorted, int [,]a)
{
// For Array pointer
int index = 0;
// k - starting row index
// m - ending row index
// l - starting column index
// n - ending column index
int k = 0, l = 0;
while (k < m && l < n)
{
// Print the first row
// from the remaining rows
for (int i = l; i < n; ++i)
{
a[k, i] = Sorted[index];
index++;
}
k++;
// Print the last column
// from the remaining columns
for (int i = k; i < m; ++i)
{
a[i, n - 1] = Sorted[index];
index++;
}
n--;
// Print the last row
// from the remaining rows
if (k < m)
{
for (int i = n - 1; i >= l; --i)
{
a[m - 1, i] = Sorted[index];
index++;
}
m--;
}
// Print the first column
// from the remaining columns
if (l < n)
{
for (int i = m - 1; i >= k; --i)
{
a[i, l] = Sorted[index];
index++;
}
l++;
}
}
}
// Function to convert 2D array to 1D array
public static int[] convert2Dto1D(int [,]y,
int m, int n)
{
int index = 0;
int []x = new int[m * n];
// Store value 2D Matrix To 1D array
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
x[index] = y[i, j];
index++;
}
}
return x;
}
// Function to print the Matrix
public static void PrintMatrix(int [,]a,
int m, int n)
{
// Print Spiral Matrix
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(a[i, j] + " ");
}
Console.WriteLine();
}
}
// Function to sort the array
public static int[] SortArray(int []x)
{
// Sort array Using InBuilt Function
Array.Sort(x);
return x;
}
// Function to Convert given Matrix
// into sorted Spiral Matrix
public static void convertMatrixToSortedSpiral(int [,]y,
int m, int n)
{
int [,]a = new int[MAX, MAX];
int []x = new int[m * n];
x = convert2Dto1D(y, m, n);
x = SortArray(x);
ToSpiral(m, n, x, a);
PrintMatrix(a, m, n);
}
// Driver code
public static void Main(String[] args)
{
int m = 4, n = 3;
int [,]y = {{ 2, 5, 12 },
{ 22, 45, 55 },
{ 1, 6, 8 },
{ 13, 56, 10 }};
convertMatrixToSortedSpiral(y, m, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to Convert given Matrix
// into sorted Spiral Matrix
let MAX = 1000;
// Function to convert the array to Spiral
function ToSpiral(m,n,Sorted,a)
{
// For Array pointer
let index = 0;
// k - starting row index
// m - ending row index
// l - starting column index
// n - ending column index
let k = 0, l = 0;
while (k < m && l < n) {
// Print the first row
// from the remaining rows
for (let i = l; i < n; ++i) {
a[k][i] = Sorted[index];
index++;
}
k++;
// Print the last column
// from the remaining columns
for (let i = k; i < m; ++i) {
a[i][n - 1] = Sorted[index];
index++;
}
n--;
// Print the last row
// from the remaining rows
if (k < m) {
for (let i = n - 1; i >= l; --i) {
a[m - 1][i] = Sorted[index];
index++;
}
m--;
}
// Print the first column
// from the remaining columns
if (l < n) {
for (let i = m - 1; i >= k; --i) {
a[i][l] = Sorted[index];
index++;
}
l++;
}
}
}
// Function to convert 2D array to 1D array
function convert2Dto1D(y,m,n)
{
let index = 0;
let x = new Array(m * n);
// Store value 2D Matrix To 1D array
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
x[index] = y[i][j];
index++;
}
}
return x;
}
// Function to print the Matrix
function PrintMatrix(a,m,n)
{
// Print Spiral Matrix
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
document.write(a[i][j] + " ");
}
document.write("<br>");
}
}
// Function to sort the array
function SortArray(x)
{
// Sort array Using InBuilt Function
x.sort(function(a,b){return a-b;});
return x;
}
// Function to Convert given Matrix
// into sorted Spiral Matrix
function convertMatrixToSortedSpiral(y,m,n)
{
let a = new Array(MAX);
for(let i=0;i<MAX;i++)
a[i]=new Array(MAX);
let x = new Array(m * n);
x = convert2Dto1D(y, m, n);
x = SortArray(x);
ToSpiral(m, n, x, a);
PrintMatrix(a, m, n);
}
// Driver code
let m = 4, n = 3;
let y = [
[ 2, 5, 12 ],
[ 22, 45, 55 ],
[ 1, 6, 8 ],
[ 13, 56, 10 ]
];
convertMatrixToSortedSpiral(y, m, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2 5 45 55 6 22 56 8 13 12 10
Complejidad del tiempo: O(m*n)
Espacio Auxiliar: O(m*n)