剑指19-顺时针打印矩阵

Posted on | In |

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

M*N 的矩阵A，第i（0,1，...）圈 的四个坐标序列分别是A[i][i..N-2-i] 和A[i..M-2-i][N-1-i]和A[M-1-i][N-1-i..i+1]和A[M-1-i..i+1][i]，切记是闭区间。 对于每个序列，如果不存在则打印停止，其不存在的条件分别是 i>N-2-i,i>M-2-i,N-1-i<i+1,M-1-i<i+1。以第一圈为例来说明对每一圈的打印规则，是依次打印N-1个、M-1个、N-1个和M-1个。

然而按上述思路实现的代码却不可行，会漏掉数字，比如对于\(3\times 3\)或者\(3\times 5\)的矩阵。经分析知是四个坐标序列有时候会无法捕捉到某个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
            return None
        M,N = len(matrix),len(matrix[0])
        i = -1
        numlist = []
        while True:
            i += 1
            if i <= N-2-i:
                numlist.extend(matrix[i][i:N-2-i+1])
            else:
                if len(numlist) == M*N:
                    break
            if i <= M-2-i:
                for j in range(i,M-2-i+1): # 二维数组不能对同列不同行的元素进行切片，所以需要挨个访问每个元素
                    numlist.append(matrix[j][N-1-i])
            else:
                if len(numlist) == M*N:
                    break
            if N-1-i>=i+1:
                numlist.extend(matrix[M-1-i][N-1-i:i+1-1:-1])
            else:
                if len(numlist) == M*N:
                    break
            if M-1-i >= i+1:
                for j in range(M-1-i,i+1-1,-1):
                    numlist.append(matrix[j][i])
            else:
                if len(numlist) == M*N:
                    break
        return numlist

抓住三点，一个是首先计算出打印的圈数是(min(M,N)+1)//2，其次设定打印停止条件即当已经打印的数字的数量等于矩阵包含的数字个数M*N时，最后每圈打印的规则，依次打印N个、M-1个、N-1个、M-2个，有点贪心算法的意味。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        M,N = len(matrix), len(matrix[0])
        if M < 1 or N < 1:
            return None
        elif M == 1 and N == 1:
            return [matrix[0][0]]
        res = []
        for o in range((min(M,N)+1)>>1):
            res.extend([matrix[o][n] for n in range(o, N-o)])
            if len(res) == M*N: # 判断是否已经打印结束
                break
            res.extend([matrix[m][N-1-o] for m in range(o+1, M-o)])
            if len(res) == M*N:
                break
            res.extend([matrix[M-1-o][n] for n in range(o, N-o-1)[::-1]])
            if len(res) == M*N:
                break
            res.extend([matrix[m][o] for m in range(o+1, M-o-1)[::-1]])
            if len(res) == M*N:
                break
        return res

注意事项： + 上述M,N = len(matrix), len(matrix[0])的写法不完善，会有matrix或者matrix[0]不是列表的情况，会出现异常。改成 if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:return None，根据短路运算规则，可以避免程序异常。