本文首發(fā)于我的個(gè)人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-print-matrix.html 作者: Suixin
題目描述
輸入一個(gè)矩陣鸭津，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字求摇，例如享幽，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解題思路
-
自己寫(xiě)的拙劣代碼。主要思想為順時(shí)針遍歷干奢，一圈之后刪除已經(jīng)遍歷過(guò)的位置扫步，然后遞歸庐舟。需要判斷為空比較多猪半。 - 大神寫(xiě)的優(yōu)質(zhì)代碼。主要思想為遍歷第一行在旱，然后刪除第一行摇零，再逆時(shí)針旋轉(zhuǎn)矩陣，循環(huán)桶蝎。代碼簡(jiǎn)潔明了驻仅。
代碼
Python(2.7.3)
自己寫(xiě)的拙劣代碼
# -*- 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
# 下面為順時(shí)針遍歷一圈
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])
# 刪除已經(jīng)遍歷過(guò)的最外圈
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
運(yùn)行時(shí)間：40ms
占用內(nèi)存：5752k
大神寫(xiě)的優(yōu)質(zhì)代碼
# -*- coding:utf-8 -*-
class Solution:
# matrix類型為二維列表噪服，需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
while matrix:
res += matrix.pop(0)
if not matrix:
break
# 這里對(duì)matrix做逆時(shí)針旋轉(zhuǎn)，原理見(jiàn)后文
matrix = list(map(list, zip(*matrix)))[::-1]
return res
運(yùn)行時(shí)間：66ms
占用內(nèi)存：5644k
矩陣的三種操作：轉(zhuǎn)置胜茧、順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn)
二維數(shù)組矩陣轉(zhuǎn)置
matrix = list(map(list, zip(*matrix)))
原理：
Python3中的zip()函數(shù)是將兩個(gè)或多個(gè)序列逐元素組合輸出粘优，返回迭代器。如：
x, y = [1, 2, 3], [4, 5, 6]
z = zip(x, y)
for i in z:
print(i)
輸出：
(1, 4)
(2, 5)
(3, 6)
而如果在zip函數(shù)內(nèi)的參數(shù)前加上*呻顽，則執(zhí)行反操作（認(rèn)為對(duì)已經(jīng)組合過(guò)的迭代器還原）雹顺。如：
z1 = zip(*z)
for i in z1:
print(i)
輸出：
(1, 2, 3)
(4, 5, 6)
那么對(duì)于矩陣的轉(zhuǎn)置，我們可以利用這個(gè)逆操作芬位，認(rèn)為原始矩陣已經(jīng)被組合過(guò)了无拗，再zip(*)操作即可返回組合前的東西（即矩陣的轉(zhuǎn)置）。而zip()的組合形式為tuple昧碉，故外層的map()和list()只是為了還原二維列表的形式而已英染。如：
matrix = [[1, 2, 3], [4, 5, 6]]
matrix = list(map(list, zip(*matrix)))
print(matrix)
輸出即為原矩陣的轉(zhuǎn)置：
[[1, 4], [2, 5], [3, 6]]
二維數(shù)組矩陣順時(shí)針旋轉(zhuǎn)
matrix = list(map(list, zip(*matrix[::-1])))
原理：可以發(fā)現(xiàn)，對(duì)矩陣先上下翻轉(zhuǎn)被饿，再轉(zhuǎn)置相當(dāng)于順時(shí)針旋轉(zhuǎn)四康。
二維數(shù)組矩陣逆時(shí)針旋轉(zhuǎn)
matrix = list(map(list, zip(*matrix)))[::-1]
原理：可以發(fā)現(xiàn)，對(duì)矩陣先轉(zhuǎn)置狭握，再上下翻轉(zhuǎn)相當(dāng)于逆時(shí)針旋轉(zhuǎn)闪金。
參考
https://blog.csdn.net/Sun_Hui_/article/details/81298544
https://docs.python.org/3/library/functions.html#zip
