c – 在矩阵中将0放在包含0的单元格的行和列中,而不使用额外的空格

概述给定一个矩阵,如果一个单元格包含0,那么我们将整个行和列对应于该单元格为0.例如,如果 1 2 3M = 0 4 5 4 2 0 那么输出应该是 0 2 0 0 0 0 0 0 0 我认为的方法如下 >创建辅助数组row []和col [].如果单元格(i,j)包含0,则将row [i]和col [j]标记为0.(最初row []和col []包含全1). 给定一个矩阵,如果一个单元格包含0,那么我们将整个行和列对应于该单元格为0.例如,如果

1 2 3M  =  0 4 5      4 2 0

那么输出应该是

0 2 0      0 0 0      0 0 0

我认为的方法如下

>创建辅助数组row []和col [].如果单元格(i,j)包含0,则将row [i]和col [j]标记为0.(最初row []和col []包含全1).
>再次遍历整个矩阵,如果对于单元格(i,j),行[i]或col [j]中的任何一个为0,则将单元格(i,j)设置为0.

这需要O(m * n)时间和O(m n)空间.

如何在空间方面进一步优化它.欢迎任何提高时间复杂度的建议.

解决方法 啊哈,这是一个老问题.

>如果第一行没有元素,则使用一个布尔变量(isZeroInFirstRow)保存,如果第一列没有元素,则保存一个布尔变量(isZeroInFirstCol).>然后,遍历整个矩阵.如果cell(i,j)== 0,则将cell(0,j)和cell(i,0)设置为0.>遍历矩阵的第一行.如果cell(0,则将列(j)中的所有元素设置为0.>遍历矩阵的第一列.如果cell(i,0)== 0,则将row(i)中的所有元素设置为0.>如果isZeroInFirstRow == true,则将row(0)中的所有元素设置为0.>如果isZeroInFirstCol == true,则将列(0)中的所有元素设置为0.

总结

以上是内存溢出为你收集整理的c – 在矩阵中将0放在包含0的单元格的行和列中,而不使用额外的空格全部内容，希望文章能够帮你解决c – 在矩阵中将0放在包含0的单元格的行和列中,而不使用额外的空格所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。