本文概述
给定矩阵, 任务是将给定矩阵转换为已排序螺旋矩阵.
例子:
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
方法:
- 将给定的2D数组转换为1D数组。
- 排序一维数组
- 将一维转换为螺旋矩阵
- 这可以通过4个用于存储所有元素的循环来解决。每个for循环都与矩阵一起定义单个方向的移动。第一个for循环代表从左到右的运动, 而第二个爬行代表从上到下的运动, 第三个代表从右到左的运动, 第四个代表从下到上的运动。
下面是上述方法的实现:
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
输出如下:
1 2 5
45 55 6
22 56 8
13 12 10