网站流量和带宽,可以做视频剪辑兼职的网站,网站整站开发项目亮点,手机网站建设教材文章目录题目标题和出处难度题目描述要求示例数据范围进阶解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三思路和算法代码复杂度分析题目
标题和出处
标题#xff1a;矩阵置零
出处#xff1a;73. 矩阵置零
难度
3 级
题目描述
要求
给定一个 m…
文章目录题目标题和出处难度题目描述要求示例数据范围进阶解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三思路和算法代码复杂度分析题目
标题和出处
标题矩阵置零
出处73. 矩阵置零
难度
3 级
题目描述
要求
给定一个 m×n\texttt{m} \times \texttt{n}m×n 的矩阵如果一个元素为 0\texttt{0}0则将其所在行和列的所有元素都设为 0\texttt{0}0。
请使用原地算法。
示例
示例 1 输入matrix[[1,1,1],[1,0,1],[1,1,1]]\texttt{matrix [[1,1,1],[1,0,1],[1,1,1]]}matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]\texttt{[[1,0,1],[0,0,0],[1,0,1]]}[[1,0,1],[0,0,0],[1,0,1]]
示例 2 输入matrix[[0,1,2,0],[3,4,5,2],[1,3,1,5]]\texttt{matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]]}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]]\texttt{[[0,0,0,0],[0,4,5,0],[0,3,1,0]]}[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
数据范围
mmatrix.length\texttt{m} \texttt{matrix.length}mmatrix.lengthnmatrix[0].length\texttt{n} \texttt{matrix[0].length}nmatrix[0].length1≤m,n≤200\texttt{1} \le \texttt{m, n} \le \texttt{200}1≤m, n≤200-231≤matrix[i][j]≤231−1\texttt{-2}^\texttt{31} \le \texttt{matrix[i][j]} \le \texttt{2}^\texttt{31} - \texttt{1}-231≤matrix[i][j]≤231−1
进阶
一个直观的解决方案是使用 O(mn)\texttt{O(mn)}O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(mn)\texttt{O(m n)}O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗
解法一
思路和算法
最直观的做法是找到矩阵中所有等于 000 的元素对于每个元素 000将其所在行和列的所有元素置零。
如果直接在原矩阵中将元素置零则无法判断等于 000 的元素是原始值等于 000 还是被置零因此需要创建辅助矩阵辅助矩阵和原矩阵的大小相同辅助矩阵中的每个元素表示原矩阵中的该元素是否置零。
遍历原矩阵对于原矩阵中每个等于 000 的元素将辅助矩阵中相应位置的相同行和相同列的元素都设为置零。然后再次遍历原矩阵和辅助矩阵对于辅助矩阵中置零的位置将原矩阵中相应位置的元素置零。
代码
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean[][] zero new boolean[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {for (int k 0; k n; k) {zero[i][k] true;}for (int k 0; k m; k) {zero[k][j] true;}}}}for (int i 0; i m; i) {for (int j 0; j n; j) {if (zero[i][j]) {matrix[i][j] 0;}}}}
}复杂度分析 时间复杂度O(mn(mn))O(mn(m n))O(mn(mn))其中 mmm 和 nnn 分别是矩阵 matrix\textit{matrix}matrix 的行数和列数。需要遍历矩阵两次第一次遍历需要将元素 000 所在行和列的所有元素标为置零每个元素需要 O(mn)O(m n)O(mn) 的处理时间第二次遍历将矩阵中的标为置零的元素置零每个元素需要 O(1)O(1)O(1) 的处理时间因此总时间复杂度是 O(mn(mn))O(mn(m n))O(mn(mn))。 空间复杂度O(mn)O(mn)O(mn)其中 mmm 和 nnn 分别是矩阵 matrix\textit{matrix}matrix 的行数和列数。需要创建和原矩阵大小相同的辅助矩阵记录原矩阵中的每个元素是否置零。
解法二
思路和算法
解法一的时间复杂度和空间复杂度都较高可以优化。
由于矩阵中每个元素 000 所在行和列的所有元素需要置零因此只需要记录矩阵的每一行和每一列是否需要置零即可。
创建两个哈希表分别记录矩阵的每一行和每一列是否需要置零遍历矩阵一次对于每个等于 000 的元素在两个哈希表中分别记录其所在行和列需要置零遍历结束之后即可得到所有需要置零的行和列。然后再次遍历矩阵对于每个元素如果两个哈希表中至少有一个哈希表记录了该元素所在的行或列需要置零则将该元素置零。
实现方面可以用两个数组分别记录矩阵的每一行和每一列是否需要置零。
代码
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean[] rows new boolean[m];boolean[] columns new boolean[n];for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {rows[i] true;columns[j] true;}}}for (int i 0; i m; i) {for (int j 0; j n; j) {if (rows[i] || columns[j]) {matrix[i][j] 0;}}}}
}复杂度分析 时间复杂度O(mn)O(mn)O(mn)其中 mmm 和 nnn 分别是矩阵 matrix\textit{matrix}matrix 的行数和列数。需要遍历矩阵两次第一次遍历需要将元素 000 所在行和列在两个哈希表中记录每个元素需要 O(1)O(1)O(1) 的处理时间第二次遍历将矩阵中的标为置零的元素置零每个元素需要 O(1)O(1)O(1) 的处理时间因此总时间复杂度是 O(mn)O(mn)O(mn)。 空间复杂度O(mn)O(m n)O(mn)其中 mmm 和 nnn 分别是矩阵 matrix\textit{matrix}matrix 的行数和列数。需要创建两个哈希表或数组分别记录矩阵的每一行和每一列是否需要置零各需要 O(m)O(m)O(m) 和 O(n)O(n)O(n) 的空间。
解法三
思路和算法
解法二仍需要 O(mn)O(m n)O(mn) 的额外空间。如果要将空间复杂度降低到 O(1)O(1)O(1)必须在矩阵内部记录每一行和每一列是否需要置零。
在矩阵内部记录置零信息可以使用第 000 行和第 000 列记录。第 000 行的一个元素如果是 000则表示该元素所在列需要置零第 000 列的一个元素如果是 000则表示该元素所在行需要置零。
如果直接修改矩阵的第 000 行和第 000 列的元素则无法记录矩阵的第 000 行和第 000 列是否需要置零因此需要使用两个变量分别记录矩阵的第 000 行和第 000 列是否需要置零。
矩阵置零的完整过程如下。 遍历矩阵的第 000 行和第 000 列记录矩阵的第 000 行和第 000 列是否需要置零。 遍历矩阵的其余元素指除了第 000 行和第 000 列的全部元素下同对于每个等于 000 的元素将其所在行的第 000 列的元素和所在列的第 000 行的元素置零。 再次遍历矩阵的其余元素对于每个元素如果一个元素所在的行或列需要置零则将该元素置零。 如果矩阵的第 000 行需要置零则将矩阵的第 000 行元素全部置零如果矩阵的第 000 列需要置零则将矩阵的第 000 列元素全部置零。
如果矩阵的第 000 行或第 000 列的一个元素原本就是 000则该元素所在行和列需要置零上述解法同样适用于该情况。
代码
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length, n matrix[0].length;boolean rowZero false, columnZero false;for (int j 0; j n; j) {if (matrix[0][j] 0) {rowZero true;break;}}for (int i 0; i m; i) {if (matrix[i][0] 0) {columnZero true;break;}}for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i][j] 0) {matrix[i][0] 0;matrix[0][j] 0;}}}for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}if (rowZero) {for (int j 0; j n; j) {matrix[0][j] 0;}}if (columnZero) {for (int i 0; i m; i) {matrix[i][0] 0;}}}
}复杂度分析 时间复杂度O(mn)O(mn)O(mn)其中 mmm 和 nnn 分别是矩阵 matrix\textit{matrix}matrix 的行数和列数。最多需要遍历矩阵中的每个元素两次。 空间复杂度O(1)O(1)O(1)。
