当前位置：首页 > article >正文

leetcode hot100_part6_矩阵

article 2025/3/9 21:13:01

矩阵篇

73.矩阵置零

要求原地算法，空间复杂度为O(1);

一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。–摘自维基百科。

O(m+n)：主要的问题是，先置零的元素会影响后续0元素的判断，会覆盖掉。可以记录所有0所在的行和列的集合（或者用数组标记）；然后再遍历集合对行列置零就行。

O(1)：根据原地算法的定义，我们需要把行和列的标记数组放到原数组中覆盖掉原数组的数据。行和列的标记数组分别放在第一行和第一列中，然后原来的第一行和第一列是否含0单独标记；

标记第一行和第一列是否为0；
在第一行和第一列中记录剩余矩阵行列是否为0；
更新剩余矩阵
更新第一行和第一列

建议看一下官方解法的代码更好理解；想一下为什么第一行和第一列的更新放到最后执行？

54.螺旋矩阵

一圈一圈的遍历，同时设置上下左右四个遍历的边界，在遍历每个边界之后及时更新边界并判断是否边界错位（重合可以的），说明遍历完了。

代码看看记得；

. - 力扣（LeetCode）参考这个和官方题解第二种

48.旋转图像

评论区一个主要的方法，先转置（行列交换）代码不会你真是sb，然后再对每一行的元素顺序进行翻转

//转置
for(int i = 0; i < row; i++){
    for(int j = i; j < column; j++){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
}

官方题解的方法，找到 matrix[i][j] 变换后的下一个位置，是matrix[ j ][ n-i-1 ]（n是列数）；弄一个新的矩阵copy；

或者是找个临时变量temp，找到旋转规律的四个坐标，直接套一下上面的就可以，还要找到旋转那一块的元素才能覆盖整个矩阵。这个空间复杂度就是O（1）；

还有个方法就是先上下翻转，然后再按主对角线翻转，得到最后结果。