73 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

方法一：拷贝出一个同样大小的矩阵，根据拷贝矩阵在原矩阵上修改元素；   空间复杂度O(mn)

方法二：第一次遍历用row记录第几行需要被改变，用column记录第几列需要被改变；第二次遍历再修改，若当前行需要被改变，直接全置零，若当前行不需要被改变，再改变当前行中被列上的0影响的元素；    空间复杂度O(m+n)，时间复杂度O(2mn)

因为第二次遍历时需要查找值，用了集合；

class Solution(object):def setZeroes(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""row, column = set(), set()m, n = len(matrix), len(matrix[0])for i in range(m):for j in range(n):if matrix[i][j] == 0:row.add(i)column.add(j)        for i in range(m):if i in row:matrix[i] = [0] * nelse:for j in column:matrix[i][j] = 0return matrix

官方思路：用第一行记录行改变情况（第一行为row），用第一列记录列改变情况（第一列为column）损失的第一行和第一列信息用变量储存；只需要记录第一行第一列是否有0即可，若有0，更新后的状态需要全0，即损失的初始状态不重要；若无0，更新后的状态只会受到该行或该列的影响，所以提前置零记录该行或该列情况不影响最终结果；     空间复杂度O(1)

class Solution(object):def setZeroes(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""row, column = 1, 1m, n = len(matrix), len(matrix[0])for i in range(n):                   #第一行情况if matrix[0][i] == 0: row = 0for i in range(m):                   #第一列情况if matrix[i][0] == 0: column = 0for i in range(1,m):                 #记录需要改变的行和列for j in range(1,n):if matrix[i][j] == 0:matrix[0][j] = 0matrix[i][0] = 0for i in range(1,m):                 #根据记录修改行和列for j in range(1,n):if matrix[0][j] == 0 or matrix[i][0] == 0:matrix[i][j] = 0if row == 0:                         #更新第一行for i in range(n):matrix[0][i] = 0if column == 0:                      #更新第一列for i in range(m):matrix[i][0] = 0return matrix

54 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

分析：一定会转满min(m//2, n//2)圈，最后不剩/剩一行/剩一列/剩一个中心元素；

思路一：直接模拟

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""out = []n, m = len(matrix), len(matrix[0])up, left, down, right = 0, 0, n-1, m-1for i in range(min(m,n)//2):for j in range(left,right+1):out.append(matrix[up][j])up += 1for j in range(up,down+1):out.append(matrix[j][right])right -= 1for j in range(right,left-1,-1):out.append(matrix[down][j])down -= 1for j in range(down,up-1,-1):out.append(matrix[j][left])left += 1if min(m,n) % 2 != 0:if n > m:for j in range(up,down+1):out.append(matrix[j][right])elif n < m:for j in range(left,right+1):out.append(matrix[up][j])else:out.append(matrix[n//2][m//2])return out

思路二：循环用while true，直至指针交错（相等是允许的）才退出；

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""res = []if matrix is None: return restop,bottom,left,right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1while True:for i in range(left,right+1): #➡️res.append(matrix[top][i])top += 1 if top > bottom: breakfor i in range(top,bottom+1): #⬇️res.append(matrix[i][right])right -= 1if right < left: breakfor i in range(right,left-1,-1): #⬅️res.append(matrix[bottom][i])bottom -= 1if bottom < top: breakfor i in range(bottom,top-1,-1): #⬆️res.append(matrix[i][left])left += 1if left > right: breakreturn res

思路三：利用zip和*的搭配实现行列的转换； 原第一行取完后，将列转行再倒序，就能取到原最后一列；由于倒序操作改变了原行内的相对位置，恰好满足原最后一行的倒序输出；

这是真牛！！！

class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""out = []while matrix:out += matrix.pop(0)matrix = list(zip(*matrix))[::-1]   return out

48 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

分析：观察旋转图像发现，其实就是转置再翻转

转置：list(zip(*))     [( )( )( )]     

           list(map(list, zip(*matrix))) == list(row) for row in zip(*matrix)     [[ ][ ][ ]]

翻转：[::-1]

class Solution(object):def rotate(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""matrix[:] = [row[::-1] for row in zip(*matrix)]

240 搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列；每列的元素从上到下升序排列。

分析：利用 matrix 特性减少搜索时间：

小于当前行起始值，就不可能再在后续中找到；

大于当前行终止值，该行不遍历；

在当前行的范围内，小于当前列值，后续就只能在较小的列中寻找；大于当前列值，继续遍历；

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""if target < matrix[0][0] or target > matrix[-1][-1]:return Falsem, n = len(matrix), len(matrix[0])for i in range(m):if target < matrix[i][0]:return Falseelif target > matrix[i][-1]:continueelse:for j in range(n):if target < matrix[i][j]:n = jelif target == matrix[i][j]:return Trueelse:continuereturn False

官方思路：从矩阵的右上角开始Z字遍历；

当目标值大于这个值，目标值就不能在当前行被找到；

当目标值小于这个值，目标值就不能在当前列被找到；

class Solution:def searchMatrix(self, matrix, target):m, n = len(matrix), len(matrix[0])i, j = m - 1, 0while i >= 0 and j < n:if matrix[i][j] == target:return Trueelif matrix[i][j] < target:j += 1else:i -= 1return False