[剑指Offer]顺时针打印矩阵

题目描述

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

解题思路

  1. 自己写的拙劣代码。主要思想为顺时针遍历,一圈之后删除已经遍历过的位置,然后递归。需要判断为空比较多。
  2. 大神写的优质代码。主要思想为遍历第一行,然后删除第一行,再逆时针旋转矩阵,循环。代码简洁明了。

代码

Python(2.7.3)

自己写的拙劣代码

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
34
35
36
37
38
39
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表,需要返回列表
def printMatrix(self, matrix):
# write code here
if len(matrix) == 1:
return matrix[0]
res = []
if len(matrix[0]) == 1:
for i in matrix:
res.append(i[0])
return res
# 下面为顺时针遍历一圈
for i in matrix[0]:
res.append(i)
for j in matrix[1:]:
res.append(j[-1])
m = matrix[-1][:-1]
m.reverse()
for k in m:
res.append(k)
m = matrix[1:-1]
m.reverse()
for l in m:
res.append(l[0])
# 删除已经遍历过的最外圈
matrix.pop()
if matrix:
matrix.pop(0)
new_matrix = []
for m in matrix:
m.pop()
m.pop(0)
if len(m) != 0:
new_matrix.append(m)
# 如果剩余矩阵不空,则递归
if new_matrix != []:
res += self.printMatrix(new_matrix)
return res

运行时间:40ms
占用内存:5752k

大神写的优质代码

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表,需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
while matrix:
res += matrix.pop(0)
if not matrix:
break
# 这里对matrix做逆时针旋转,原理见后文
matrix = list(map(list, zip(*matrix)))[::-1]
return res

运行时间:66ms
占用内存:5644k

矩阵的三种操作:转置、顺时针旋转和逆时针旋转

二维数组矩阵转置

1
matrix = list(map(list, zip(*matrix)))

原理:
Python3中的zip()函数是将两个或多个序列逐元素组合输出,返回迭代器。如:

1
2
3
4
x, y = [1, 2, 3], [4, 5, 6]
z = zip(x, y)
for i in z:
print(i)

输出:

1
2
3
(1, 4)
(2, 5)
(3, 6)

而如果在zip函数内的参数前加上*,则执行反操作(认为对已经组合过的迭代器还原)。如:

1
2
3
z1 = zip(*z)
for i in z1:
print(i)

输出:

1
2
(1, 2, 3)
(4, 5, 6)

那么对于矩阵的转置,我们可以利用这个逆操作,认为原始矩阵已经被组合过了,再zip(*)操作即可返回组合前的东西(即矩阵的转置)。而zip()的组合形式为tuple,故外层的map()list()只是为了还原二维列表的形式而已。如:

1
2
3
matrix = [[1, 2, 3], [4, 5, 6]]
matrix = list(map(list, zip(*matrix)))
print(matrix)

输出即为原矩阵的转置:

1
[[1, 4], [2, 5], [3, 6]]

二维数组矩阵顺时针旋转

1
matrix = list(map(list, zip(*matrix[::-1])))

原理:可以发现,对矩阵先上下翻转,再转置相当于顺时针旋转。

二维数组矩阵逆时针旋转

1
matrix = list(map(list, zip(*matrix)))[::-1]

原理:可以发现,对矩阵先转置,再上下翻转相当于逆时针旋转。

参考

https://blog.csdn.net/Sun_Hui_/article/details/81298544
https://docs.python.org/3/library/functions.html#zip