Leetcode 刷题记录 06 —— 矩阵

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

目录

01 矩阵置零

方法一：标记数组

方法二：两个标记变量

02 螺旋矩阵

方法一：模拟

方法二：按层模拟

03 旋转图像

方法一：辅助数组

方法二：原地旋转

方法三：用翻转代替旋转

04 搜索二维矩阵 Ⅱ

方法一：直接查找

方法二：二分法

方法三：Z字形查找

---

01 矩阵置零

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {}
};

方法一：标记数组

时间复杂度 O(mn)，空间复杂度 O(m + n)

• 建立两个数组 row(m) 和 col(n)，存储 matrix 中行和列的含零情况

• 遍历数组，判断行或列含零，执行 matrix[i][j] = 0

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<int> row(m), col(n);for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(!matrix[i][j]){row[i] = true;col[j] = true;}}}for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(row[i] || col[j]){matrix[i][j] = 0;}}}}
};

① vector<int> row(m), col(n);这俩数组没有初始化啥的吗，它们声明时的默认元素值是多少？

使用 vector<int> row(m) 这样的语句声明一个 vector并指定大小时， vector会自动初始化为指定大小的元素，且每个元素默认初始化为零。

方法二：两个标记变量

时间复杂度 O(mn)，空间复杂度 O(1)

• 建立两个标记 flag_col0 和 flag_row0，存储 matrix 中除第零行和第零列的含零情况

• 遍历数组，判断 !matrix[i][0] || !matrix[0][j]，执行 matrix[i][j] = 0

• 第零行和第零列单独更新

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size(); //一共m行int n = matrix[0].size(); //一共n列int flag_col0 = false, flag_row0 = false;for(int i=0; i<m; ++i){if(!matrix[i][0]) flag_col0 = true;}for(int j=0; j<n; ++j){if(!matrix[0][j]) flag_row0 = true;}//处理大部分元素for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][j]){matrix[i][0] = 0;matrix[0][j] = 0;}}}for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}//处理第零行、第零列元素if(flag_col0){for(int i=0; i<m; ++i){matrix[i][0] = 0;}}if(flag_row0){for(int j=0; j<n; ++j){matrix[0][j] = 0;}}}
};

02 螺旋矩阵

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {}
};

方法一：模拟

时间复杂度 O(mn)，空间复杂度 O(mn)

• 建立二维数组 visited(rows, vector<bool>(columns)，存储矩阵元素的访问情况

• 遍历矩阵，判断 nextRow 和 nextColumn 是否越过边界

class Solution {
public:static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //向右、下、左、上vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) return {};int rows = matrix.size(), columns = matrix[0].size(), total = rows * columns;vector<vector<bool>> visited(rows, vector<bool>(columns)); //标记vector<int> order(total); //答案int row = 0, column = 0, dirIndex = 0;for(int i=0; i<total; i++){order[i] = matrix[row][column]; //更新答案visited[row][column] = true; //更新标记int nextRow = row + dirs[dirIndex][0];int nextColumn = column + dirs[dirIndex][1];if(nextRow >= rows || nextRow < 0 || nextColumn >= columns || nextColumn < 0 || visited[nextRow][nextColumn]){dirIndex = (dirIndex + 1) % 4;}row += dirs[dirIndex][0];column += dirs[dirIndex][1];}return order;}
};

① static 意味着变量在程序的生命周期内只会被分配一次，并且在所有对该数组的函数调用中共享同一存储空间。

② constexpr 用于指定变量值在编译时就确定下来，它提示编译器尽量进行优化。

③ {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}每一对元素代表在二维平面上一个方向的坐标变换：

• {0, 1}：代表向右移动 —— 行不变，列加一

• {1, 0}：代表向下移动 —— 行加一，列不变

• {0, -1}：代表向左移动 —— 行不变，列减一

• {-1, 0}：代表向上移动 —— 行减一，列不变

④ vector<bool>(columns) 创建一个布尔向量，大小为 columns，其中每个元素默认初始化为 false。

⑤ vector<vector<bool>>(rows, ...) 表示创建一个这样的布尔向量的向量，其长度为 rows，即每一行都是一个布尔向量，且每列都是初始化为 false。

⑥ spiral 螺旋形的 constexpr 常量表达式

⑦ 在什么样的情况下 if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) 中的 nextRow < 0 成立？

由于初始位置是 (0, 0) 且遍历顺序是顺时针螺旋，因此 nextRow < 0 通常在当前方向反转尝试向上之前使用过的路径上被访问时发生。

⑧ 将代码中涉及 nextRow 和 nextColumn 部分的片段改为如下片段如何？

if((column == (columns - 1)) || (row == (rows - 1)) || (column == 0) || matrix[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]){dirIndex = (dirIndex + 1) % 4;
}

 matrix[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]：这种方式不仅增加了代码复杂度，并且可能由于超出 matrix 的边界而导致访问无效内存，出现内存错误。

if (column == columns || row == rows || column == -1 || row == -1 ||
row + dirs[dirIndex][0] < 0 || row + dirs[dirIndex][0] >= rows ||
column + dirs[dirIndex][1] < 0 || column + dirs[dirIndex][1] >= columns || 
visited[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]) {
dirIndex = (dirIndex + 1) % 4;
}

row + dirs[dirIndex][0] < 0：检查向当前方向移动后，新的行索引是否小于0。这会保持我们不越过上边界。

row + dirs[dirIndex][0] >= rows：检查向当前方向移动后，新的行索引是否大于或等于总行数。这会确保我们不越过下边界。

column + dirs[dirIndex][1] < 0：检查向当前方向移动后，新的列索引是否小于0。这会确保我们不越过左边界。

column + dirs[dirIndex][1] >= columns：检查向当前方向移动后，新的列索引是否大于或等于总列数。这会确保我们不越过右边界。

方法二：按层模拟

时间复杂度 O(mn)，空间复杂度 O(1)

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size() == 0 || matrix[0].size() == 0) return {};vector<int> order;int rows = matrix.size(), columns = matrix[0].size();int left = 0, right = columns-1, top = 0, bottom = rows-1;//主打一个遍历while(left<=right && top<=bottom){for(int column=left; column<=right; ++column) {order.push_back(matrix[top][column]);}for(int row=top+1; row<=bottom; ++row) {order.push_back(matrix[row][right]);}if(left<right && top<bottom){for(int column=right-1; column>=left+1; --column) {order.push_back(matrix[bottom][column]);}for(int row=bottom; row>=top+1; --row) {order.push_back(matrix[row][left]);}}top++;left++;right--;bottom--;}return order;}
};

① 为什么还要第二次判断 if(left<right && top<bottom) 呢？

在只有一行或者一列剩下时，第二次顺时针迭代会导致重复元素被添加到结果中。例如，当只剩下一行时，上面的第二次和第三次迭代（从右向左）会和已经处理的行产生重复。比如：

• 单行（例如，[[1, 2, 3]]）

• 单列（例如，[[1], [2], [3]]）

03 旋转图像

class Solution {
public:void rotate(vector<vector<int>>& matrix) {}
};

方法一：辅助数组

时间复杂度 O(n^2)，空间复杂度 O(n^2)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {auto matrix_new = matrix;int n = matrix.size();for(int i=0; i<n; ++i){for(int j=0, j<n; ++j){matrix_new[j][n-1-i] = matrix[i][j];}}return matrix_new;}
};

auto matrix_new = matrix;这行代码的作用是复制matrix变量的值到一个新的变量matrix_new中，matrix_new的类型与matrix一致。

对于大多数与标准库相关的容器（如 std::vector），这会创建 matrix 的一个浅拷贝，整体上是深拷贝其内容，而不是仅仅复制指针（如果它是一个复杂数据结构）。

方法二：原地旋转

时间复杂度 O(n^2)，空间复杂度 O(1)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<(n+1)/2; ++y){int flag = matrix[x][y];matrix[x][y] = matrix[n-1-y][x];matrix[n-1-y][x] = matrix[n-1-x][n-1-y];matrix[n-1-x][n-1-y] = matrix[y][n-1-x];matrix[y][n-1-x] = flag;}}}
};

方法三：用翻转代替旋转

时间复杂度 O(n^2)，空间复杂度 O(1)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<n; ++y){swap(matrix[x][y], matrix[n-1-x][y]);}}for(int x=0; x<n; ++x){for(int y=0; y<x; ++y){swap(matrix[x][y], matrix[y][x]);}}}
};

04 搜索二维矩阵 Ⅱ

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {}
};

方法一：直接查找

时间复杂度 O(mn)，空间复杂度 O(1)

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto& row: matrix){for(int element: row){if(element == target) return true;}}return false;}
};

方法二：二分法

时间复杂度 O(mlogn)，空间复杂度 O(1)

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto& row: matrix){auto it = lower_bound(row.begin(), row.end(), target);if(it != row.end() && *it == target) return true;}return false;}
};

lower_bound 是一个标准库函数，位于 <algorithm> 头文件中，用于在一个已排序的范围内查找目标值的位置。lower_bound 返回一个迭代器，指向范围内第一个不小于目标值的元素的位置，如果所有的元素都小于目标值，它将返回指向末尾的迭代器。

注意：使用 lower_bound  的前提是 row 必须是排序好的，否则结果是不确定的。

方法三：Z字形查找

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int x = 0, y = n-1;while(x < m && y >=0){if(matrix[x][y] == target) return true;else if(matrix[x][y] > target) y--;else x++;}return false;}
};

文章部分代码来源于力扣（LeetCode）