Geek Answers Handbook

In the matrix, put 0 in the row and column of the cell that contains 0 without using additional space

If a matrix is ​​given, if the cell contains 0, then we make the whole row and column corresponding to the cell, like 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

  • Make auxiliary arrays row[] and col[] . If cell (i, j) contains 0, then mark row[i] and col[j] as 0. (Initially, row[] and col[] contain all 1s).
  • Cross the entire matrix again if for cell (i, j), any of row[i] or col[j] is 0, then put cell (i, j) at 0.

It takes O (m * n) and O (m + n) time.

How to optimize it additionally specifically in terms of space. Suggestions for improving time complexity are also welcome.

+6
source share
6 answers

Yeah, this is an old question.

  • Use one boolean variable ( isZeroInFirstRow ) if the first row has a null element or not and one boolean exponent ( isZeroInFirstCol ) if the first column has a null element or not.

  • Then go through the entire matrix. If cell(i,j)==0 , then set cell (0, j) and cell (i, 0) to 0.

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

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

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

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

+10
source

You can solve this in O (1) space. One solution is to iterate over the matrix, for every 0 you see that the corresponding line / col fills some character, for example, "X".

When you're done, you should end up with something like this:

  X 2 X M= 0 XX XX 0

Then you iterate over the matrix again and replace each "X" with 0 to get:

  0 2 0 M= 0 0 0 0 0 0
+1
source

If you are interested in storage, you might consider using a small matrix of storage formats to store the resulting matrix, and then release the original input density.

An example of what I propose could be the following (using the COO format), which should take O (M * N) time:

 #include<vector> #include<iostream> #include<algorithm> #include<cstddef> using namespace std; int main() { constexpr size_t M = 3; constexpr size_t N = 3; int matrix[M][N] = { {1, 2, 3}, {0, 4, 5}, {4, 2, 0} }; vector<size_t> markedRows; vector<size_t> markedColumns; // Search for zeroes for (size_t ii = 0; ii < M; ++ii) { for(size_t jj = 0; jj < N; ++jj) { if (matrix[ii][jj] == 0) { markedRows.push_back (ii); markedColumns.push_back(jj); } } } // Sort columns (rows are ordered by construction) sort(markedColumns.begin(),markedColumns.end()); // Eliminate duplicates markedRows.erase (unique(markedRows.begin() ,markedRows.end()) ,markedRows.end() ); markedColumns.erase(unique(markedColumns.begin(),markedColumns.end()),markedColumns.end()); // Construct COO matrix format vector<size_t> irow; vector<size_t> icol; vector<int> val; for (size_t ii = 0; ii < M; ++ii) { for(size_t jj = 0; jj < N; ++jj) { if ( ( find(markedRows.begin() ,markedRows.end() ,ii) == markedRows.end() ) && ( find(markedColumns.begin(),markedColumns.end(),jj) == markedColumns.end() ) ) { irow.push_back(ii); icol.push_back(jj); val.push_back (matrix[ii][jj]); } } } // FROM HERE YOU NO LONGER NEED MATRIX, AND YOU CAN FREE THE STORAGE // Print non zero entries for( size_t ii = 0; ii < irow.size(); ++ii) { cout << "A["<<irow[ii]<<","<<icol[ii]<<"] = "<<val[ii]<<endl; } return 0; }
+1
source

You can use your algorithm without highlighting and an auxiliary row or column by searching matirx for a row that does not contain zeros and a column that does not contain zero elements.

If any of these searches fail, then the resulting matrix will be zeros, so your work will be done by simply setting all the elements to zero.

Otherwise, use the row and colum that you found as the row and column of the bookkeeping that you mentioned, setting the corresponding element to zero when you find zeros in the rest of the matrix. Once this pass has been completed, you will walk along the line of bookkeeping, setting the matix columns to zeros for any zero found in the line of bookkeeping, similarly for the aux column.

0
source

Here the algorithm can do this in O (M * N) time and O (1) space: -

  • Find the maximum element in the matrix.
  • Mat [i] [j] = max - Mat [i] [j] for all (i, j)
  • Note that Mat [i] [j] will only have positive values.
  • Use negetive values ​​as sentinels and Mat [i] [j] = max as zeros.
  • Get initial values ​​in the form Mat [i] [j] = max - Mat [i] [j]
0
source

Simple and easy answer: <2 nested loops> to search all columns and rows you will find any cell = 0 through the entire column and set it to zeros across the entire row and set it to zeros. let me know if it is not clear to record a video.

 Int main() { //example matrix dimension rows(r=6) * columns (c=3) int r = 6; int c = 3; int matrix[r][c]; for(int i=0; i<r; ++i){ for(int j=0 ; j < c ; ++j){ if(matrix[i][j] == 0){ for(int ii=0; ii<r; ++ii){ Matrix[ii][j] = 0 ; } for(int jj=0; jj<c; ++jj){ Matrix[i][jj] = 0 ; } } } } }
0
source

More articles:


All Articles