Golang:
声明:这题我首先用了JAVA语言去实现,在通过所有测试用例后,发现结果如下:
我觉得我实现的超烂,时间复杂度上(我预估)是超烂,空间复杂度上(从程序里就能看出来)也是超烂,结果这个程序的时间复杂度这么好?
思路:因为我今天是第一次做这道题,所以在所有算法里我可能会先写暴力一点的算法,即先做出来,再考虑优化。先上暴力求解的思路,即通过循环来实现,我们可以很明显的看出,螺旋式,其实就像剥洋葱一样,是一层一层地去剥的,我们可以拆解为,先输出最外圈,再输出内圈,当第一层外圈被输出后,第二层内圈即变成原来的外圈,于是就可以一直输出。
具体实现:我们可以考虑三种类型的二维数组,行数远大于列数的,列数远大于行数的,以及行数等于列数的。
那么问题有:
- 一共要剥几层?
在这里我认为,最多要剥min(m,n)/2+1
层。这里大家可以简单用几个数组自己试一下即可。 - 怎么剥?
螺旋式的剥,数组先向右,再向下,再向左,最后向上。 - 每一层剥到什么时候结束
这个其实是关键问题,我采用的方法是,用另外一个同等大小的二维数组flag
,每当我们访问了一次matrix[x][y]
后,就将flag
数组同等位置写成1,如果二维数组是n*n
的,那么螺旋式输出,直至回到起始值为止。如果不是,我们去判断下flag[x][y]
的值,如果它是1,那么说明该结束了。
Tips:如果你在一个循环里,定义变量x
自增,希望x
到达n
时停止循环,那用x<n
这一判断条件会好于x!=n
代码明天再补。。。
有疑问加站长微信联系(非本文作者)