蛇形遍历(Diagonal Traverse)

Posted on In

Input:

[[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]]

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)