描述

题目描述

给定我们一个$nn$，然后让我们输出我们一个$n\ast nn\; *\; n$的一个矩阵，然后顺序是按照顺时针方向排列

样例解释

样例输入

3

样例输出是

[[1,2,3],[8,9,4],[7,6,5]]

题解

解法一：直接模拟

解题思路

这个可以看一下，我上面的样例解释，就是这个题目的思路

我们可以直接按照题目种的要求，直接模拟即可，如我上图的箭头的顺序

代码实现

class Solution {
public: 
    vector<vector<int> > Matrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int left = 0, right = n - 1, up = 0, down = n - 1;
//         这个是左边右边上边下边
        int begin = 1, end = n * n;
//         开始和结尾
        while (begin <= end) {
            for (int i = left; i <= right; i++) res[up][i] = begin++;
//             遍历从左到右
            up++;
            for (int i = up; i <= down; i++) res[i][right] = begin++;
//             从上到下
            right--;
            for (int i = right; i >= left; i--) res[down][i] = begin++;
//             从右到左
            down--;
            for (int i = down; i >= up; i--) res[i][left] = begin++;
//             从下到上
            left++;
        }
        return res;
//         这个跟我样例解释的一样
    }
};

时空复杂度分析

时间复杂度： $O(n^2)O(n\; ^\; 2)$

理由如下：我们需要遍历我们整个的数组，所以就是数组大小

空间复杂度： $O(1)O(1)$

理由如下：答案数组不计入空间复杂度，其余只引用的常数级别的空间

解法二： 定义我们的方向向量

实现思路

事实上，我们可以采用一种巧妙的方式，我们用二维数组表示我们上下左右的四个方向，然后我们让我们开始的位置从左上角开始，初始方向设置为向右， 如果访问的位置超过了矩阵的边界或者之前访问过了，我们就要进入下一个方向，如此反复遍历所有的之后结束

代码实现

class Solution {
   public:
    vector<vector<int>> Matrix(int n) {
        int maxNum = n * n, cur = 1;
//         开始和结尾的值
        vector<vector<int>> a(n, vector<int>(n, 0));
//         答案数组
        int row = 0, column = 0, begin = 0;
//         循环中遍历的变量
        vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//         我们的方向向量
        while (cur <= maxNum) {
            a[row][column] = cur++;
            int nxtRow = row + dir[begin].first,
                nxtColumn = column + dir[begin].second;
//             我们下一次的方向
            if (nxtRow < 0 || nxtRow >= n || nxtColumn < 0 || nxtColumn >= n ||
                a[nxtRow][nxtColumn] != 0) {
                begin = (begin + 1) % 4;  // 顺时针旋转至下一个方向
            }
            row += dir[begin].first, column += dir[begin].second;
//             时刻更新我们的方向
        }
        return a;
    }
};

时空复杂度分析

时间复杂度： $O(n^2)O(n\; ^\; 2)$

理由如下：我们需要遍历我们整个的数组，所以就是数组大小

空间复杂度： $O(1)O(1)$

理由如下：答案数组不计入空间复杂度，其余只引用的常数级别的空间