leetcode hot100_part6_矩阵

矩阵篇

73.矩阵置零

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

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

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

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

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

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

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）；

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

       

240.搜索二维矩阵||

        之前做的简单的版本好像是两次二分就可以了；这个不是简单的两次二分；数字特征不一样

        每行遍历，对每行都进行二分法查找；

        或者用排除法. - 力扣（LeetCode），灵神的这个很好懂啊，也就是官解Z字查找

四个题目搞完，感觉矩阵这块手有点生