将给定矩阵转换为排序的螺旋矩阵

2021年4月28日19:57:51 发表评论 906 次浏览

本文概述

给定矩阵, 任务是将给定矩阵转换为已排序螺旋矩阵.

例子:

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: