【算法笔记】5.LeetCode-Hot100-矩阵专项

发布于:2025-07-10 ⋅ 阅读:(23) ⋅ 点赞:(0)

1. 矩阵置零(t73)

中等难度,题目示例如下:

给定一个 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,就将其行和列标记为true,最后再遍历一次矩阵,对标记的部分置零。

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

2. 螺旋矩阵(t54)

中等难度,题目示例如下:

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

思路分析:可以从两个角度去考虑,第一个角度是从纯数理的方式去找规律,比如转向等操作可以通过对宽高取模来判断,但理解起来较抽象;第二个角度是直接从矩阵结构入手,用四个变量去跟踪矩阵的边界,下面以这个思路进行求解。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if (matrix.empty()) return ans;

        int rows = matrix.size();
        int cols = matrix[0].size();
        int up = 0, down = rows - 1;
        int left = 0, right = cols - 1;

        while (true) {
            // 向右
            for (int i = left; i <= right; i++) {
                ans.push_back(matrix[up][i]);
            }
            up++;
            if (up > down) break;

            // 向下
            for (int i = up; i <= down; i++) {
                ans.push_back(matrix[i][right]);
            }
            right--;
            if (right < left) break;

            // 向左
            for (int i = right; i >= left; i--) {
                ans.push_back(matrix[down][i]);
            }
            down--;
            if (down < up) break;

            // 向上
            for (int i = down; i >= up; i--) {
                ans.push_back(matrix[i][left]);
            }
            left++;
            if (left > right) break;
        }

        return ans;
    }
};

3. 旋转图像(t48)

中等难度,题目示例如下:

给定一个 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]]

思路分析:这题最简单的思路就是直接找旋转的图像的规律,仔细观察就可以发现,旋转这个操作,等价于对角线翻转+左右翻转。下面稍微注意的是,做对角线翻转只需要遍历矩阵的上三角。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        
        // 对角线翻转
        for (int i = 0; i < rows; i++){
            for (int j = i; j < cols; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        
        // 左右翻转
        for (int i = 0; i < rows; i++){
            for (int j = 0; j < cols / 2; j++){
                swap(matrix[i][j], matrix[i][cols - 1 - j]);
            }
        }
    }
};

4. 搜索二维矩阵 II(t240)

中等难度,题目示例如下:

编写一个高效的算法来搜索 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 的值,就提前跳出,节省时间。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        for (int i = 0; i < rows; i++){
            for (int j = 0; j < cols; j++){
                if (matrix[i][j] == target) return true;
                else if (matrix[i][j] > target) break; 
            }
        }
        return false;
    }
};

题目中,每行每列都已经是排序好的,因此显然存在更优方案,看了用户 Krahets 的题解恍然大悟,把矩阵逆时针旋转 45°,就变成了类似二叉搜索树的结构。

图源:https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/2361487/240-sou-suo-er-wei-ju-zhen-iitan-xin-qin-7mtf/

因此,可以从矩阵的左下角出发,如果左下角大于target,则往上移动一行,如果小于target,则可以直接往右搜索。

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

网站公告

今日签到

点亮在社区的每一天
去签到