73. 矩阵置零
给定一个 _m_ x _n_ 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
**输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
两次遍历，第一次遍历记录元素等于0的位置i,j;第二次遍历，判断是否和i、j同行、同列，来决定是否设置为0.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
#获取矩阵的行
row = len(matrix)
#获取矩阵的列
col = len(matrix[0])
#设置行列标签数组
row_label = [False] * row
col_label = [False] * col
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
row_label[i] = True
col_label[j] = True
for i in range(row):
for j in range(col):
if row_label[i] or col_label[j]:
matrix[i][j] = 0
54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
**输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
定义边界，然后先从左到右，访问结束后，重新定义边界，判断边界是否覆盖，覆盖则结束；然后依次按照螺旋顺序访问。
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m,n = len(matrix), len(matrix[0])
upper, left, right, down = 0, 0, n-1, m-1
ans = []
while True:
#from left to right
for i in range(left, right+1): ans.append(matrix[upper][i])
upper += 1
if upper > down:break
# from top to down
for i in range(upper, down+1): ans.append(matrix[i][right])
right -= 1
if right < left:break
# from right to left
for i in range(right, left-1,-1): ans.append(matrix[down][i])
down -= 1
if down < upper:break
# from down to top
for i in range(down, upper-1, -1): ans.append(matrix[i][left])
left += 1
if left > right:break
return ans
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector <int> ans;
if(matrix.empty()) return ans; //若数组为空，直接返回答案
int u = 0; //赋值上下左右边界
int d = matrix.size() - 1;
int l = 0;
int r = matrix[0].size() - 1;
while(true)
{
for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
if(-- r < l) break; //重新设定有边界
for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
if(-- d < u) break; //重新设定下边界
for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
if(++ l > r) break; //重新设定左边界
}
return ans;
}
};
48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
想办法通过多次调整实现，翻转or置换，即通过多次简单操作实现最终复杂的结果。需要细心观察，找到规律。
1 2 3 7 8 9 7 4 1
4 5 6 先上下对折，得到 4 5 6 再对角线交换，得到 8 5 2
7 8 9 1 2 3 9 6 3
所以，实现步骤 1，上下对折；2，对角线交换
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
rows, cols = len(matrix), len(matrix[0])
for i in range(cols):
for j in range(rows//2):
matrix[j][i], matrix[rows-j-1][i] = matrix[rows-j-1][i], matrix[j][i]
for i in range(rows):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 _m_ x _n_ 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
一种思路，双层循环，遍历每一个元素，确定是否存在target。时间复杂度高，同时没有利用到行间有序，列内有序的特性。
因此，想找到一个行和列组成的有序数组，减少不必要的遍历操作。以右上角为例，第一行和最后一列可以组成一个有序数组，通过判断角上的元素与target，可以缩小查找范围：
- nums(i, j) < target: 第i行不用找了
- nums(i, j) > target: 第j列不用找了
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
x, y = 0, n - 1
while x < m and y >= 0:
if matrix[x][y] == target:
return True
if matrix[x][y] > target:
y -= 1
else:
x += 1
return False
