刷题小计六：矩阵

73.矩阵置零 mid

矩阵置零 

①先使用两个变量（row_0 & col_0），记录「首行 & 首列」是否该被置零

②在「非首行首列」的位置，存储置零信息到首行首列

        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

置零，遍历第二次

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

④使用 r0 & c0 ，置零「首行 & 首列」 

54.螺旋矩阵 mid

螺旋矩阵

循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。
根据边界打印，即 将元素按顺序添加至列表 res 尾部。
边界向内收缩 1 （代表已被打印）。
判断边界是否相遇（是否打印完毕），若打印完毕则跳出。

48.旋转图像 mid

旋转图像

对于矩阵任意第 i 行、第 j 列元素 matrix[i][j] ，矩阵旋转 90º 后「元素位置旋转公式」为：

由于第 1 步 D→A 已经将 A 覆盖（导致 A 丢失），此丢失导致最后第 4 步 A→B 无法赋值。为解决此问题，考虑借助一个「辅助变量 tmp 」预先存储 A 

根据开头的元素旋转公式：

int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = temp;

当矩阵大小 n 为偶数时，取前 n / 2行、前  n / 2  列的元素为起始点；

当矩阵大小 n 为奇数时，取前  n / 2行、前  (n + 1) / 2  列的元素为起始点； 风车型旋转

 

复杂度分析

时间复杂度 O(N ^2) ： 其中 N 为输入矩阵的行（列）数。需要将矩阵中每个元素旋转到新的位置，即对矩阵所有元素操作一次，使用 O(N ^ 2) 时间。
空间复杂度 O(1) ： 临时变量 tmp 使用常数大小的额外空间。值得注意，当循环中进入下轮迭代，上轮迭代初始化的 tmp 占用的内存就会被自动释放，因此无累计使用空间。 

部分图文作者：Krahets
链接：https://leetcode.cn/problems/rotate-image/solutions/1228078/48-xuan-zhuan-tu-xiang-fu-zhu-ju-zhen-yu-jobi/
来源：力扣（LeetCode）

240.搜索二维矩阵 mid

搜索二维矩阵 II

抽象二叉搜索树

原文地址：https://blog.csdn.net/Gus10124/article/details/142818681

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！