螺旋矩阵算法 Posted on 2021-07-09 00:00:00 2021-07-09 00:00:00 by Author 摘要 这个螺旋转圈的算法，可以转晕很多人(包括我在内） # 螺旋矩阵算法 ------------------- 写于2021/05/19 --------------------- 1. 题目描述： 给定一个正整数 n，生成一个包含 1 到 n*n 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 2. 示例描述： - 示例一： - 输入：3 - 输出： - [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] - 示例二： - 输入：4 - 输出： - [1, 2 , 3, 4] - [12,13,14, 5] - [11,16,15, 6] - [10, 9, 8, 7] 3. 解题思路： - 本题主要的难点在于：1.怎么按照顺时针由外到内填充n行n列的二维矩阵。2.怎么防止填充时数组下标越界问题。3. 对于n*n的二位数组考虑n为奇数和偶数时怎么填充的问题。 - 首先，分析可知，当n为偶数时，循环n/2圈之后就能把整个数组填充完毕，当n为奇数时，循环n/2圈完时，还有数据中心位置需要填充，而数组中心位置就是num[n/2]][n/2]的位置。其次，就是顺时针转圈填充数组时需要注意，遵循左闭右开原则，同时应该怎么顺时针填充数组尼，这里分别定义每一圈起始位置的x,y下标（即为startX,startY)，同时找到一个可以控制每次循环保证左闭右开的一个限制变量offset，使得每次循环都能保证左闭右开且保证填充数组不越界等问题，初始值为1（因为是左闭右开原则所以，offeset初始值设置为1）,最后分别顺时针填充数组元素。 - 填充方式如下：即先从左到右填充横行，这里注意填充时循环次数为（n+start - offset： 保证每次数组不越界，同时遵从左闭右开原则，这个可以动笔算一下），接下来由上到下填充纵行，这里的循环次数和横行类似（startx+n-offset）,接下来就是从右到左逆向填充横行，这里循环条件比较简单（i>startX）,最后就是从下到上填充纵行，这里循环条件也比较简单（j>starY）,这就顺时针循环一圈了，同时为了保证下次能够正确填充数组，startX和startY都斜向下移动一格，offset=offset+2(为什么加2，不加一尼，解释：由于上次填充了一圈所以offset先加一，同时又要保证左闭右开原则，所以offset又要加一，所以offset=offset+2))，以上就是转一圈的整个流程。什么时候转圈完毕尼，即为Loop圈减为0时，循环完毕。最后根据n为奇数还偶数做相应的处理即可。具体流程，见如下代码。 4.代码实现： ~~~java public int[][] generateMatrix(int n) { //定义一个n*n为数组 int[][] result = new int[n][n]; //转圈的次数 int loop = n / 2; //开始转圈的起始位置 int startX = 0; int startY = 0; //保证左闭右开同时数组下标不越界的控制变量 int offset = 1; //所经过数组的步数，即为数组要填充的元素的值的变量 int count = 1; //判断是奇数还是偶数，方便最后的处理 int mid = n / 2; //需要转的圈数 while (loop > 0) { //每一圈的起始位值 int i = startX; int j = startY; //从左到右横向填充（注意循环条件） for (; j < n + startY - offset; j++) { result[startX][j] = count++; } //从上到下纵向填充（也要注意循环条件） for (; i < startX + n - offset; i++) { result[i][j] = count++; } //从右到左横向填充(循环条件比较简单，即纵坐标大于起始纵坐标即可) for (; j > startY; j--) { result[i][j] = count++; } //从下到上纵向填充(循环条件比较简单，即横坐标大于起始横坐标即可) for (; i > startX; i--) { result[i][j] = count++; } //一圈结束，圈数减一 loop--; //重新定位起始坐标 startX++; startY++; //重新更改控制变量的值 offset = offset + 2; } //如果是奇数，还要填充中间位置 if (n % 2 == 1) { result[mid][mid] = count; } //返回最终结果 return result; } ~~~
{{ item.content }}
{{ child.content }}