使用O（1）额外空间打印n x n螺旋矩阵-yiteyi-C++库

给定一个数字n，使用O（1）空间按顺时针方向打印一个n x n螺旋矩阵（从1到n x n的数字）。

null

例子：

Input: n = 5Output:25 24 23 22 2110  9  8  7 2011  2  1  6 1912  3  4  5 1813 14 15 16 17

我们强烈建议您尽量减少浏览器，并先自己尝试。 如果允许额外的空间，解决方案就会变得简单。我们为nxn矩阵分配内存，对于从n*n到1的每个元素，我们开始按螺旋顺序填充矩阵。为了保持螺旋顺序，使用了四个循环，每个循环用于矩阵的上、右、下和左角。

但如何在O（1）空间中求解呢？ nxn矩阵具有ceil（n/2）平方圈。一个循环由第i行，（n-i+1）第列，（n-i+1）第行和第i列组成，其中i从1到ceil（n/2）变化。

25 24 23 22 21 10 9  8  7  2011 2  1  6  1912 3  4  5  1813 14 15 16 17

第一个循环由其第一行、最后一列、最后一行和第一列的元素组成（标记为红色 )第一个循环由n*n到（n-2）*（n-2）+1的元素组成。i、 e.从25岁到10岁。
第二个循环由第二行、第二末列、第二末行和第二列的元素组成（标记为蓝色 )第二个循环由（n-2）*（n-2）到（n-4）*（n-4）+1的元素组成。i、 e.从9点到2点。
第三个循环由第三行、最后第三列、最后第三行和第三列的元素组成（标记为黑色 ).第三个循环由（n-4）*（n-4）到1的元素组成。i、 e.只有1个。

我们的想法是，对于每一个正方形周期，我们都将一个标记与之关联。对于外部循环，标记的值为0，对于第二个循环，标记的值为1，对于第三个循环，标记的值为2。通常，对于nxn矩阵，第i个循环的标记值为i–1。如果我们把矩阵分成两部分，右上三角形（用橙色 )和左下三角形（用绿色 )，然后使用标记x，我们可以使用以下公式轻松计算任何n x n螺旋矩阵中的指数（i，j）处的值——

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)

下面是这个想法的实施。

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	 "                                     , (n-2*x)*(n-2*x) - (i-x)                       
                                                 - (j-x));                       
           
                                                 // for lower left half                       
                                                 else                       
                                                 printf                                     (                                     "%d	 "                                     , (n-2*x-2)*(n-2*x-2) + (i-x)                       
                                                 + (j-x));                       
                                                 }                       
                                                 printf                                     (                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5;                       
           
                                                 // print a n x n spiral matrix in O(1) space                       
                                                 printSpiral(n);                       
           
                                                 return                                     0;                       
                         }                       

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) +                                     "	"                                     );                       
           
                                                 // for lower left half                       
                                                 else                       
                                                 System.out.print((n -                                     2                                     * x -                                     2                                     ) * (n -                                     2                                     * x -                                     2                                     ) +                       
                                                 (i - x) + (j - x) +                                     "	"                                     );                       
                                                 }                       
                                                 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                                     =                                     "	"                                     )                       
           
                                                 # For lower left half                       
                                                 else                                     :                       
                                                 print                                     (((n                                     -                                     2                                     *                                     x                                     -                                     2                                     )                                     *                       
                                                 (n                                     -                                     2                                     *                                     x                                     -                                     2                                     )                                     +                       
                                                 (i                                     -                                     x)                                     +                                     (j                                     -                                     x)), end                                     =                                     "	"                                     )                       
                                                 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) +                                     "	"                                     );                       
           
                                                 // for lower left half                       
                                                 else                       
                                                 Console.Write((n - 2 * x - 2) *                       
                                                 (n - 2 * x - 2) +                       
                                                 (i - x) + (j - x) +                                     "	"                                     );                       
                                                 }                       
                                                 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                                     "	 "                                     , (                                     $n                                     - 2 *                                     $x                                     ) *                       
                                                 (                                     $n                                     - 2 *                                     $x                                     ) -                       
                                                 (                                     $i                                     -                                     $x                                     ) - (                                     $j                                     -                                     $x                                     );                       
           
                                                 // for lower left half                       
                                                 else                       
                                                 echo                                     "	 "                                     , (                                     $n                                     - 2 *                                     $x                                     - 2) *                       
                                                 (                                     $n                                     - 2 *                                     $x                                     - 2) +                       
                                                 (                                     $i                                     -                                     $x                                     ) + (                                     $j                                     -                                     $x                                     );                       
                                                 }                       
                                                 echo                                     ""                                     ;                       
                                                 }                       
                         }                       
           
                         // 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

运动对于给定的数字n，使用O（1）空间以逆时针方向打印一个n x n螺旋矩阵。本文由 阿迪蒂亚·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章