技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

Leetcode-刷题记录-06-矩阵

 收录于 未分类
   约 2257 字   预计阅读 5 分钟 
https://bing.ee123.net/img/rand?artid=146140221

Leetcode 刷题记录 06 —— 矩阵

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

01 矩阵置零

https://i-blog.csdnimg.cn/direct/564c443e83e143809f639b5eeefbd705.png

https://i-blog.csdnimg.cn/direct/031d00a6bbe146d5b44dd36d085f471e.png

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 螺旋矩阵

https://i-blog.csdnimg.cn/direct/2a6590655d0146b38234f95c9d92a114.png

https://i-blog.csdnimg.cn/direct/3f80deca66d94c66aa44a1e079c6e6a6.png

https://i-blog.csdnimg.cn/direct/09b1f85a644f42a0b06ee983ec4bb1e8.png

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)

https://i-blog.csdnimg.cn/direct/9262c23fe44845d6aef47642d1a29ac2.png

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 旋转图像

https://i-blog.csdnimg.cn/direct/f9b300b77c7e4893bcaeea497b826a5c.png

https://i-blog.csdnimg.cn/direct/c6a60202cecc4717867e919a50891ff8.png

https://i-blog.csdnimg.cn/direct/d6dbabb2c39649b2977d5e85a805a451.png

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)

https://i-blog.csdnimg.cn/direct/f835ff428e474c2abf1b14a38a936080.png

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)

https://i-blog.csdnimg.cn/direct/e3a3d41eb06a4f02907af69767af0de9.png

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 搜索二维矩阵 Ⅱ

https://i-blog.csdnimg.cn/direct/ee8051787487479d8cc52c65fe1d5fb2.png

https://i-blog.csdnimg.cn/direct/c4e0aac56ee44df9922c62f7c24d95e6.png

https://i-blog.csdnimg.cn/direct/fb727f3a1c8a4e87bd27b58ebe277221.png

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）

更新于 2025-03-09
 算法, 笔记, 矩阵, 哈希算法, Leetcode, C
返回 | 主页