# 使用`O(1)`額外空間打印 n x n 螺旋矩陣 > 原文： [https://www.geeksforgeeks.org/print-n-x-n-spiral-matrix-using-o1-extra-space/](https://www.geeksforgeeks.org/print-n-x-n-spiral-matrix-using-o1-extra-space/) 給定數字 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 ``` **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 如果允許額外的空間，則解決方案變得簡單。 我們為 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 ``` 1. 第一個循環由其第一行，最后一列，最后一行和第一列（用紅色標記）組成。 第一個循環包含從 n * n 到（n-2）*（n-2）+ 1 的元素，即從 25 到 10。 2. 第二周期由第二行，倒數第二列，倒數第二行和第二列（由 blue 標記）組成。 第二個周期由（n-2）*（n-2）至（n-4）*（n-4）+ 1 組成，即 9 至 2。 3. 第三循環由第三行，倒數第三列，倒數第三行和第三列（由**黑色**標記）組成。 第三個周期包含從（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++ ```cpp // 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\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; } ```