原矩阵 顺时针取值,
得到新的结果数组
下面是我的思路过程,有可能开始就想复杂了,导致中间需要创建很多辅助矩阵
创建一个辅助顺序矩阵(对应原矩阵的每个元素的最终顺序 ),
顺序矩阵 然后在遍历原矩阵的时候,对照对应位置的顺序矩阵给结果数组赋值。
得到顺序矩阵
思路:上图顺序矩阵中的 17 其实对应的顺序中间矩阵中的第二个圈的第一个数字 1,1 如何变成 17,17=1+第一个圈的长度( 16 ),每一个圈的长度都有一定的规律,
缩写下:2*(currentColumnNum+currentLineNum)-4
数字意义: 长+宽+长+宽-重复计算的部分
这里第三圈的外圈长度等于第一圈长度+第二圈的长度,第四也是如此依次递推,所以需要一个递推函数,单独计算外圈的总长度
outSideLength = countOutSideLength({lineLength,columnLength,currentCircleNo})
得到圈数矩阵的过程
根据原矩阵初始化一个矩阵
转换成最后转换成圈数矩阵
得到顺序中间矩阵的过程
用上面得到的圈数矩阵复制然后扩充得到一个新的矩阵
遍历内圈判断每个元素位于圈的上,右,下,左用一定规律得到顺序中间矩阵
得到顺序矩阵
遍历上面得到的顺序中间矩阵,每个元素加上外圈的总长度得到顺序矩阵(这部可以和上一步骤合并,在上一个的遍历内圈时同时加上外圈的总长度)
得到结果数组
初始化结果数组为一个长度为原矩阵的长*宽的数组,遍历顺序矩阵 ,将对应的行和列的原矩阵
赋值给结果数组(比如顺序矩阵的第 4 行的第三列的对应的是 22,那么结果数组的( 22-1 )个元素为原矩阵的第 4 行的第三列对应的 13 )
1
steel1990 2018-02-24 18:22:30 +08:00 via Android
用一个标记记录当前遍历的方向,方向按顺时针变化就好了啊。
|
2
moonmagian 2018-02-24 18:24:17 +08:00 via Android
实际上只存在左至右,上至下,右至左,下至上四个按顺序遍历的过程,实际上在每一轮这样的遍历,进行遍历时都比上次遍历少得到两个数,那么可以使用一个记录当前位置的变量,直接一圈一圈地得到结果数组,应该也是一种思路
|
3
imlink OP @moonmagian 应该是没一轮少 4,少了 4 个角。这确实是个方法。
|
4
akira 2018-02-24 18:37:14 +08:00
1l 2l 的方法就可以了,只是具体实现的方法有好几个,随便一个都比你现在的要好
|
5
ant2017 2018-02-24 18:38:07 +08:00 via Android
取第一行,旋转矩阵,取第一行,旋转矩阵…
|
6
swulling 2018-02-24 18:49:51 +08:00 via iPad
确实复杂了。
|
7
abusizhishen 2018-02-24 18:50:20 +08:00 via Android
懵逼中
|
8
akira 2018-02-24 18:51:10 +08:00
另外,这种题目感觉应该可以通过纯数学方式来解答的,可惜现在矩阵什么的 完全还给老师了。。
|
9
imlink OP 脑回路太复杂,其实一开始也是有想过 2 楼的方案,觉得遍历的时候的变量太多放弃了。最后选择了更复杂的方案。
|
10
acros 2018-02-24 19:06:10 +08:00 via iPhone
按一楼的空间 n,时间 n,不是很方便吗,还有其他要求?
|
11
awolfly9 2018-02-24 19:11:37 +08:00 via Android
这个问题还是我司的面试题
|
12
akira 2018-02-24 19:13:58 +08:00
已知以下数列
1 1 2 4 3 1 2 3 6 9 8 7 4 5 请尝试给出此数列的数学描述 @@ |
14
liuhaotian 2018-02-24 19:23:18 +08:00
<script src="https://gist.github.com/VEXIO/699426f1fda739aed04a3b9fd3cc1646.js"></script>
|
15
taifus 2018-02-24 19:55:16 +08:00 via Android 1
蛇形数组 🤓
|
16
vindurriel 2018-02-24 19:57:00 +08:00 via iPhone
这不就是贪吃蛇么?往一个方向走 越界或者撞墙就右转
|
17
mdluo 2018-02-24 20:16:35 +08:00
|
18
mdluo 2018-02-24 20:25:28 +08:00
@mdluo #17 上面这个代码处理边界条件有些问题,仅提供个思路,有时间你可以自己修复
p 表示当前在处理第几条边 nav 表示当前边( p%4 )的两个相邻元素之间的索引位置差值 count 用来记录当前边( p%2 )的剩余元素个数 |
19
sun1991 2018-02-24 20:27:05 +08:00
类似寻路算法, 撞墙或者撞到以前访问过的节点, 就右转 90 度不就行了嘛
|
20
kaifeii 2018-02-24 20:31:19 +08:00
对于 n,m 矩阵,直接建 n*m 的数组,然后遍历矩阵,对于第 i 行第 j 列:
i>j : i,j-> (n+m-2(j+1))*2*(j+1)-(j-1-i) i=j : i,j-> (n+m-2j)*2*(j)+1 i<j : i,j-> (n+m-2i)*2*i+j-i+1 直接赋值 |