【题目】
给定一个整型矩阵 matrix,请按照转圈的方式打印它。
例如:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
打印结果为:1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
要求额外空间复杂度为O(1).
【基本思路】
一层一层的打印矩阵。在矩阵中用左上角(tR, tC)和右下角(dR, dC)就可以表示一个子矩阵。比如,题目中的矩阵,当(tR, tC) = (0,0), (dR, dC) = (3,3)。表示的子矩阵就是整个矩阵,它的最外圈的部分如下:
1 2 3 4
5 8
9 12
13 14 15 16
转圈把这个外层打印出来,然后令tR, tC加1,dR, dC减1,这时所表示的子矩阵就是:
6 7
10 11
继续转圈打印出来即可。
def spiralOrderPrint(arr):
tr = tc = 0
#(tr,tc)为数组左上角的坐标,开始0行0列
dr = len(arr)-1
#dr 表示右下角行的坐标索引,len(arr)代表数组行数 -1为索引
dc = len(arr[0])-1
#dc 表示右下角列的索引 len(arr[0])表示每行有几个元素 -1为索引
while tc<=dc and tr<=dr:
#条件确保左列不超过右列。确保下行不超过上行
if tr == dr:
for i in range(tc,dc+1):
print(arr[tr][i],end=' ')
elif tc==dc:
for i in range(tr,dr+1):
print(arr[i][tc],end=' ')
else:
for i in range(tc,dc):
print(arr[tr][i],end=' ')
for i in range(tr,dr):
print(arr[i][dc],end=' ')
for i in range(dc,tc,-1):
print(arr[dr][i],end=' ')
for i in range(dr,tr,-1):
print(arr[i][tc],end=' ')
tc+=1
tr+=1
dc-=1
dr-=1
if __name__ == '__main__':
li = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
spiralOrderPrint(li)