以矩阵放0，其中包含0的小区的行和列中，而无需使用额外的空间 [英] In a matrix put 0 in the row and column of a cell which contains 0 without using extra space

问题描述

给定的矩阵中，如果一个单元包含0，那么我们必须使对应于单元整个行和列0。例如，如果

Given a matrix, if a cell contains 0, then we have make entire row and column corresponding to the cell as 0. For example, if

      1 2 3
M  =  0 4 5
      4 2 0

那么输出应该是

then the output should be

      0 2 0
      0 0 0
      0 0 0

我想的方法如下：

The method I thought is as follows

1. 请辅助阵列行[] 和 COL [] 。如果单元格（I，J）包含0，那么，标记行[I] 和 COL [J] 为0 （最初行[]和 COL [] 包含全1）。
2. 同样遍历整个矩阵，如果细胞（I，J），无论是的行[I] 或 COL [J] 0，然后把细胞（I，J）为0。

1. Make auxiliary arrays row[] and col[]. If a cell(i,j) contains 0 then, mark row[i] and col[j] as 0.(Initially row[] and col[] contains all 1s).
2. Again traverse the whole matrix, if for cell(i,j), either of row[i] or col[j] is 0, then put cell(i,j) as 0.

这需要O（M * N）的时间和O（M + N）的空间。

This takes O(m*n) time and O(m+n) space.

如何优化它进一步特意在space.Any建议方面改善的时间复杂度也受到了欢迎。

How to optimize it further specially in terms of space.Any suggestions for improving time complexity are also welcomed.

推荐答案

啊哈，这是一个老问题。

Aha, this is an old question.

1. 使用一个布尔值变动内容（ isZeroInFirstRow ）储蓄，如果第一行的零元（S）或不和一个布尔值变动内容（ isZeroInFirstCol ）节省如果第一列的零元（S）或没有。

1. Use one boolean variate(isZeroInFirstRow) saving if first row has zero element(s) or not and one boolean variate(isZeroInFirstCol) saving if first column has zero element(s) or not.

然后，遍历整个矩阵。如果单元（I，J）== 0 ，然后设置单元格（0，j）和单元（I，0）为0。

Then, traverse the whole matrix. If cell(i,j)==0, then set cell(0,j) and cell(i,0) to 0.

遍历矩阵的第一行。如果单元（0，J）== 0 ，然后设置在列（J）的所有元素为0。

Traverse the first row of the matrix. If cell(0,j)==0, then set all elements in column(j) to 0.

遍历矩阵的第一列。如果单元（I，0）== 0 ，然后设置在行（i）所有元素为0。

Traverse the first column of the matrix. If cell(i,0)==0, then set all elements in row(i) to 0.

如果 isZeroInFirstRow ==真，设置行中的所有元素（0）0。

If isZeroInFirstRow==true, set all elements in row(0) to 0.

如果 isZeroInFirstCol ==真，设置列中的所有元素（0）0。

If isZeroInFirstCol==true, set all elements in column(0) to 0.

这篇关于以矩阵放0，其中包含0的小区的行和列中，而无需使用额外的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！