蛇形遍历(Diagonal Traverse)

Input:

[[ 1, 2, 3 ],]

Output: [1,2,4,7,5,3,6,8,9]

Explanation:

upload successful

像蛇爬行一样沿着对角线来回遍历整个矩阵。

提供一种很容易实现的解题思路:

在遍历过程中有几种情况:向右遍历、向下遍历、向左下遍历、向右上遍历。

给定两个变量x,y(记做matrix[x][y])记录当前坐标,就能通过判断这几个方向决定下一个坐标位置。

例如,向左下遍历即x++,y--,如果x已经到矩阵下边界则转向右遍历;如果x未到矩阵下边界,y到矩阵左边界则向下遍历;如果xy都未到矩阵边界则继续向左下遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
state,x,y,M,N = 'right_up',0,0,len(matrix),len(matrix[0])
if state == 'left_down':
rs.append(matrix[x][y])
if x == M-1 or y == 0:
if x == M-1:
y += 1
state = 'right_after_left_down'
else:
x += 1
state = 'down_after_left_down'
else:
x += 1
y -= 1

依次类推,可以将所有情况与边界情况都列出来。

同时需要排除三种特殊情况:当矩阵为空时不存在遍历结果;当矩阵行或列为1时直接将矩阵从上至下遍历。

经简化可写出解法(result):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findDiagonalOrder(matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if matrix == []:return []
rs,state,x,y,M,N = [],0,0,0,len(matrix),len(matrix[0])
if M == 1 or N == 1:return reduce(lambda x,y:x+y,matrix)
while True:
rs.append(matrix[x][y])
if x == M-1 and y == N-1:return rs
elif state == 0:
if x == 0 or y == N-1:
if y == N-1:x,state = x+1,2
else:y,state = y+1,5
else:x,y = x-1,y+1
elif state == 1:
if x == M-1 or y == 0:
if x == M-1:y,state = y+1,4
else:x,state = x+1,3
else:x,y = x+1,y-1
elif state == 3 or state == 4:x,y,state = x-1,y+1,0
elif state == 2 or state == 5:x,y,state = x+1,y-1,1

其中每个元素都被处理过一遍,其时间复杂度为O(n)