原文：
给定数字n，请使用o(1)空间沿顺时针方向打印n x n螺旋矩阵（从 1 到n x n的数字）。
示例：
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
我们强烈建议您最小化浏览器，然后自己尝试。
如果允许额外的空间，则pg电子试玩链接的解决方案变得简单。 我们为n x n矩阵分配内存，并为从n * n到 1 的每个元素分配以螺旋顺序填充矩阵。 为了维持螺旋顺序，使用了四个循环，每个循环用于矩阵的顶部，右侧，底部和左侧。
但是如何在o(1)空间中解决呢？
一个n x n矩阵具有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 20
11 2 1 6 19
12 3 4 5 18
13 14 15 16 17
-
第一个循环由其第一行，最后一列，最后一行和第一列（用红色标记）组成。 第一个循环包含从
n * n到(n-2) * (n-2) 1的元素，即从 25 到 10。 -
第二周期由第二行，倒数第二列，倒数第二行和第二列（由蓝色标记）组成。 第二个周期由
(n-2) * (n-2)至(n-4) * (n-4) 1组成，即 9 至 2。 -
第三循环由第三行，倒数第三列，倒数第三行和第三列（由黑色标记）组成。 第三个周期包含从
(n-4) * (n-4)到 1 的元素，即仅 1。
这个想法是针对每个平方周期，我们将一个标记与其关联。 对于外部循环，标记的值为 0，对于第二循环，标记的值为 1，对于第三循环，标记的值为 2。通常，对于n x n矩阵，第i个循环的标记值为i – 1。
如果将矩阵分为两部分，右上三角形（由橙色标记）和左下三角形（由绿色标记），则使用标记x，我们可以使用以下公式，轻松地计算出将在任何nxn螺旋矩阵中的索引(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
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;
}
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
输出：
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螺旋矩阵。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
