LeetCode 热题 100之矩阵

1.矩阵置0

思路分析：使用标记数组

• 记录需要置为 0 的行和列：使用两个布尔数组 zeroRows 和 zeroCols 来记录需要置为 0 的行和列
• 两次遍历
  • 第一遍遍历整个矩阵，找到所有为0的元素，并更新zeroRows和zeroCols；
  • 第二遍遍历，依照zeroRows和zeroCols的状态，将对应的行和列元素置为0
  • 时间复杂度为 O(m * n)，空间复杂度为 O(m + n)，其中 m 和 n 分别是矩阵的行数和列数。

具体实现代码（详解版）：

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {if (matrix.empty()) return;int rows = matrix.size();int cols = matrix[0].size();vector<bool> zeroRows(rows,false);vector<bool> zeroCols(cols,false);//第一次遍历，记录哪些行和列需要置为0for(int i = 0 ; i < rows ; i ++){for(int j = 0 ; j < cols ;j ++){if(matrix[i][j] == 0 ){zeroRows[i] = true;//记录第i行需要置为0zeroCols[j] = true;//记录第j列需要置为0}}}//第二次遍历，根据记录的行和列将其置为0for(int i = 0 ; i < rows ; i ++){for(int j = 0 ; j < cols ;j ++){if(zeroRows[i] || zeroCols[j] ){matrix[i][j] = 0;}}}}
};

2.螺旋矩阵

思路分析：要以顺时针螺旋顺序返回一个矩阵中的所有元素，可以采用四个边界（上、下、左、右）来控制遍历的范围。具体步骤如下

• 初始化边界：设定四个变量，top,bottom,left，right，分别表示当前未遍历部分的上下左右边界
• 循环遍历
  • 从左到右遍历当前的top行，更新top边界；
  • 从上到下遍历当前的right列，更新right边界；
  • 检查是否仍有行可遍历，若有，从右到左遍历当前的bottom行，更新bottom边界；
  • 检查是否仍有列可遍历，若有，从下到上遍历当前的left列，更新left边界；
• 重复以上步骤，直到所有元素被遍历

具体实现代码（详解版）：

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> result;if(matrix.empty() || matrix[0].empty()) return result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while(top <= bottom && left <= right){//从左到右遍历上边界for(int j = left ; j <= right ; j ++){result.push_back(matrix[top][j]);}top ++;//下移//从上到下遍历右边界for(int i = top ; i <= bottom ; i ++){result.push_back(matrix[i][right]);}right --;//左移if(top <= bottom){//检查是否仍有行可遍历//从右到左遍历下边界for(int j = right ; j >= left ; j --){result.push_back(matrix[bottom][j]);}bottom --;//上移}if(left <= right){//从下到上遍历左边界for(int i = bottom ; i >= top ; i --){result.push_back(matrix[i][left]);}left ++;//右移}}return result;}
};

还有一种写法，供参考：

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;}
};

3.旋转图像

思路分析：要在原地顺时针旋转 n×n 的矩阵，可以分为两个步骤：先进行矩阵的转置，然后再对每一行进行反转。

• 转置：通过双重循环，将 matrix[i][j] 和 matrix[j][i] 进行交换，从而完成转置操作。注意这里只需遍历上三角矩阵，以避免重复交换
• 反转每一行：std::reverse 函数反转每一行，完成最终的旋转。

具体实现代码（详解版）：

void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 1. 转置矩阵for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {swap(matrix[i][j], matrix[j][i]);}}// 2. 反转每一行for (int i = 0; i < n; ++i) {reverse(matrix[i].begin(), matrix[i].end());}
}

4.搜索二维矩阵II

思路分析：使用一种从矩阵的右上角开始的搜索方法，这种方法的时间复杂度为 O(m+n)，其中 m 是矩阵的行数，n 是列数。

• 从右上角开始，设置 row 为 0，col 为最后一列的索引。
• 搜索逻辑
  • 如果当前元素等于目标值，则返回 true；
  • 如果当前元素等大于目标值，说明target在左侧，向左移动（减少列索引）；
  • 如果当前元素等小于目标值，说明target在下侧，向下移动（增加行索引）；

具体实现代码（详解版):

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {// 检查矩阵是否为空if (matrix.empty() || matrix[0].empty()) return false;int m = matrix.size();      // 矩阵行数int n = matrix[0].size();   // 矩阵列数int row = 0;                // 从第一行开始int col = n - 1;            // 从最后一列开始while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] > target) {col--; // 当前值大于目标，向左移动} else {row++; // 当前值小于目标，向下移动}}return false; // 未找到目标值}
};