[59. Spiral Matrix II]

[(https://leetcode.cn/problems/spiral-matrix-ii/)

螺旋矩阵

• 其实此题并没有设计什么灵活的算法，只是对模拟的要求高。本题需要考虑的边界条件比较多，因此需和之前所讲的Binary Search的一样，依旧需要遵循循环不变量原则，也就是左闭右开
• 模拟矩阵：由外向内
  • 上行从左往右
  • 右列从上往下
  • 下行从右往左
  • 左列从下到上
• 代码如下：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int loop = n / 2;	//遍历圈数
        int startx = 0, starty = 0;		//每次遍历开始的位置
        int offset = 1;		//限制遍历的长度，每新增一圈需要减一
        int number = 1;		//为矩阵赋值
        int i = 0, j = 0;	//i为y，j为x以此模拟
        vector<vector<int>>result( n, vector<int>( n, 0 ) );	//结果矩阵
        
        
        while(loop-- != 0)
        {
            //遍历左闭右开
            
            //上行从左到右
            for(i = starty ; i < n - offset; ++i )
            {
                result[startx][i] = number++;
            }

            //左列从上到下
            for(j = startx ; j < n - offset; ++j )
            {
                result[j][i] = number++;
            }

            //下行从右到左
            for( ; i > starty; --i )
            {
                result[j][i] = number++;
            }

            //左列从下到上
            for( ; j > startx; --j )
            {
                result[j][i] = number++;
            }

            //每遍历完一圈，起始位置的x，y都需要加一，以此准备下一圈
            ++startx;
            ++starty;
            
            //控制遍历长度
            ++offset;
        } 
        
        //若n为奇数，矩阵最中间的数我们并没有遍历，因此还需要赋值
        if( n % 2 == 1 )
        {
            result[startx][starty] = number;
        }
        return result;
    }
};

• 时间复杂度：O（n²）

  空间复杂度：O（n²）

原文地址：http://www.cnblogs.com/chenglixue/p/16783943.html