6. 矩阵
约 1679 字大约 6 分钟
LeetcodePythonC++
2025-10-10
6. 矩阵
6.1 矩阵置零
- 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]示例 2：输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示
思路：分别保存有0的行和列，然后遍历矩阵将有0的行和列赋值0。
Pythonclass Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ row_has_0 = [0 in row for row in matrix] col_has_0 = [0 in col for col in zip(*matrix)] for i, row in enumerate(row_has_0): for j, col in enumerate(col_has_0): if row or col: matrix[i][j] = 0C++class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<int8_t> row_has_0(m); vector<int8_t> col_has_0(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { row_has_0[i] = col_has_0[j] = 1; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row_has_0[i] || col_has_0[j]) { matrix[i][j] = 0; } } } } };时间复杂度：O(mn)，其中 m 和 n 分别是 matrix 的行数和列数。
空间复杂度：O(m+n)。
6.2 螺旋矩阵
- 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]示例 2：输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示
思路：用一个数组保存四个方向，判断下一个位置，行或列越界或已经访问过，那么改到下一个方向。
PythonDIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上 class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: m, n = len(matrix), len(matrix[0]) ans = [] i = j = di = 0 for _ in range(m * n): # 一共走 mn 步 ans.append(matrix[i][j]) matrix[i][j] = None # 标记，表示已经访问过（已经加入答案） x, y = i + DIRS[di][0], j + DIRS[di][1] # 下一步的位置 # 如果 (x, y) 出界或者已经访问过 if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None: di = (di + 1) % 4 # 右转 90° i += DIRS[di][0] j += DIRS[di][1] # 走一步 return ansC++class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<int> res(m * n); int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int i = 0, j = 0, dir = 0; for (int k = 0; k < m * n; k++) { res[k] = (matrix[i][j]); matrix[i][j] = INT_MAX; int x = i + DIRS[dir][0]; int y = j + DIRS[dir][1]; if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) { dir = (dir + 1) % 4; } i += DIRS[dir][0]; j += DIRS[dir][1]; } return res; } };时间复杂度：O(mn)，其中 m 和 n 分别为 matrix 的行数和列数。
空间复杂度：O(1)。返回值不计入。
6.3 旋转图像
- 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]示例 2：输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]提示
思路：顺时针旋转90°，等价先转置，再翻转每行。
Pythonclass Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # 第一步：转置 for i in range(n): for j in range(i): # 遍历对角线下方元素 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 第二步：行翻转 for row in matrix: row.reverse()C++class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { swap(matrix[i][j], matrix[j][i]); } } for (auto &row : matrix) { ranges::reverse(row); } } };重要
将两次循环优化成一次循环：上面的方法是遍历下三角，如果改成上三角就可以转置完直接翻转。
Pythonclass Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) for i, row in enumerate(matrix): for j in range(i + 1, n): # 遍历对角线上方元素，做转置 row[j], matrix[j][i] = matrix[j][i], row[j] row.reverse() # 行翻转C++class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { swap(matrix[i][j], matrix[j][i]); } ranges::reverse(matrix[i]); } } };时间复杂度：O(n2)，其中 n 是 matrix 的行数和列数。
空间复杂度：O(1)。
6.4 搜索二维矩阵 II
- 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1：
输入：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示例 2：输入：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 = 20
输出：false提示
思路：从右上角开始遍历，如果当前元素比 target 小，那么整行都比 target 小，行下移；如果当前元素比 target 大，列左移，不断逼近 target 。
Pythonclass Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) i, j = 0, n - 1 # 从右上角开始 while i < m and j >= 0: # 还有剩余元素 if matrix[i][j] == target: return True # 找到 target if matrix[i][j] < target: i += 1 # 这一行剩余元素全部小于 target，排除 else: j -= 1 # 这一列剩余元素全部大于 target，排除 return FalseC++class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); int i = 0, j = n - 1; while (i < m && j >= 0) { if (matrix[i][j] == target) { return true; } else if (matrix[i][j] > target) { j--; } else { i++; } } return false; } };时间复杂度：O(m+n)，其中 m 和 n 分别为 matrix 的行数和列数。每次循环排除掉一行或者一列，一共 m+n 行列，最坏情况下需要排除 m+n−1 行列才能找到答案。
空间复杂度：O(1)。