矩阵置0

[编程题]矩阵置0

热度指数：11032 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个m*n的矩阵，如果有一个元素是0，就把该元素所在的行和列上的元素全置为0，要求使用原地算法。

拓展：

你的算法有使用额外的空间吗？

一种比较直接的算法是利用O(m,n)的空间，但是这不是一个好的解法

使用简单的改进可以在O(m+n)的空间解决这个问题，但是还不是最佳的解法

你能在常量级的空间复杂度内解决这个问题吗？

算法知识视频讲解

华科不平凡

发表于 2020-09-25 15:23:56

利用第一行和第一列存储状态：首先记录第一行第一列中是否含有0 遍历矩阵，如果元素为0，将对应的行头和列头的元素置0 再次遍历矩阵，如果对应的行头或列头元素为0，将当前元素置0 最后，如果第一行原来就有0，将第一行置0，第一列同样操作 // // Created by jt on 2020/9/ 展开全文