LeetCode 矩阵

小结一下今天刷的LeetCode算法题，今天刷的三道题属于矩阵方面。

矩阵置零

给你一个m * n 的数组，如果一个元素的值为零，则将这个元素所在行列的全部元素置为零，要求使用原地算法。

我的思路

先遍历一次整个矩阵，用临时数组存储数组中值为零的元素的坐标，然后逐一把这些元素所在的行列的元素置为零。

• 空间复杂度 最坏情况下，矩阵中的每一个元素均为零，所需的额外空间为O(m * n)；
• 时间复杂度 同样是最坏情况下，对于每一个元素，据需要处理m + n个元素，所以时间复杂度为O((m + n) * m * n)

螺旋矩阵

给你一个矩阵，按照顺时针螺旋的顺序，返回矩阵中的所有元素。

我的思路

按照顺时针螺旋的顺序，一个个返回矩阵中的元素，设置四个边界值，分别对应右->下->左->上，每输出一轮元素后(既输出一行或者一列元素后)，就更新边界值，直到输出完所有的矩阵元素。

• 空间复杂度 使用了几个临时变量暂存下标，故空间复杂度为O(1)
• 时间复杂度 遍历一次整个矩阵，故时间复杂度为O(N²);

旋转图像

给定一个n * n的矩阵表示一个图像，将图像进行原地顺时针旋转九十度，不可使用辅助矩阵。

我的思路

观察题目给出的样子，可以发现matrix[i][j]位置的元素旋转后的位置是[j][length -i -1]；与i、j对应的四个元素之间存在这样的关系：

matrix[i][j] = matrix[length - j - 1][i]

matrix[length - j - 1][i] = matrix[length - i - 1][length - j - 1]

matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1]

matrix[j][length - i - 1] = matrix[i][j]

发现这些关系后就不难了，把这些关系代码化，放进双重for循环里既可解决这道题。

• 空间复杂度 O(1)
• 时间复杂度O(n²)

搜索二维矩阵

编写一个算法，看target值是否在矩阵中，矩阵的每行每列元素均是升序的。

我的思路

判断target是否可能在matrix[i]上，如果可能，则对这一行元素进行二分查找，否则判断下一行元素，直至找完整个矩阵。

• 空间复杂度O(1)
• 时间复杂度O(m*log₂n)