Here I come up with a better solution.
first I need 2 auxiliary link list, named Rows and Cols, in where the
"contains zero column/row" is stored.
then I scan the matrix, when finding an '0', I just insert the row and
column of this '0' into the Rows and Cols lists.
then after the first scan, tranverse the Rows and Cols lists, clear
all the Rows and Cols in the list to zero.
Best Regards,
James Fang
On 11月27日, 上午12时50分, "James Fang" <[EMAIL PROTECTED]> wrote:
> The below algorithm cost 3*O(m*n)+NumberOfInitialZeros*( O(m)+o(n) )
>
> ============================================================================
> ============================================================================
> =========
>
> No matter the array can hold other elements or not, you can always use
> auxiliary memory space to make it store more than 0&1, suppose it is a M*N
> array,
>
> initializing the auxiliary space will cost O(m*n).
>
> and the algorithm can be described as follow:
>
> for(int i=0; i<n; ++i)
>
> for(int j=0; j<m; ++j)
>
> {
>
> if( array[i][j] == 0)
>
> {
>
> for(int k=0;k<n;++k)
>
> {
>
> if( array[k][j] != 0 ) array[k][j]=-1;
>
> }
>
> for(int l=0;l<m;++l)
>
> {
>
> if( array[i][l] != 0 ) array[i][l]=-1;
>
> }
>
> array[i][j] = -1;
>
> }
> }
>
> for(int i=0;i<n;++i)
>
> for(int j=0;j<m;++j)
>
> if(array[i][j]==-1)
>
> array[i][j]=0;
>
> Best Regards,
> James Fang
>
> _____
>
> 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
> chandra kumar
> 发送时间: 2007年11月23日 21:58
> 收件人: algogeeks@googlegroups.com
> 主题: [algogeeks] Re: NxN matrix
>
> Hi, as I understood the question goes like this (I also face this problem
> earlier)...
>
> Given an array of 0s and 1s (whether the array can contain any other
> element apart from 0 and 1 is not mentioned in the question posted, but to
> make it hard people say that the array cannot hold element other then 0 and
> 1, basically a bit array ) . You need to change the given array such that
> each row and column that have a 0 initially should have all 0s in it.
>
> e.g.
>
> 1 1 1 1 1 0 1 1
>
> 1 0 1 1 0 0 0 0
>
> 1 1 1 1 ====> 1 0 1 1
>
> 1 1 1 1 1 0 1 1
>
> Thanks and Regards,
>
> K.V.Chandra Kumar
>
> On 23/11/2007, MJ <[EMAIL PROTECTED]> wrote:
>
> HI Chandra,
>
> As per the problem statement
>
> "Given an array of 0's and 1's whenever you encounter an 0 make
> corresponding column and row elements 0. "
>
> Does it mean make all the rows and column zero or only last row and
> column elemnt zero??
> could you reframe the problem statement with more details or an
> example.
>
> Thank YOu,
> Mayur
>
> On Nov 23, 1:20 pm, "chandra kumar" <[EMAIL PROTECTED]>
> wrote:
>
>
>
> > I have some questions in case 2.... questions inlined..
>
> > Thanks and regards,
> > K.V.Chandra kumar.
>
> > On 22/11/2007, Dave <[EMAIL PROTECTED]> wrote:
>
> > > Case 1
> > > Start:
> > > 0 1 1
> > > 1 1 1
> > > 1 1 1
>
> > > After first scan:
> > > 0 1 0
> > > 1 1 1
> > > 0 1 1
>
> > > After second scan:
> > > 0 1 0
> > > 0 1 1
> > > 0 1 1
>
> > > After third scan:
> > > 0 0 0
> > > 0 1 1
> > > 0 1 1
>
> > > Case 2
> > > Start:
> > > 1 1 0
> > > 1 1 1
> > > 0 1 1
>
> > > After first scan:
> > > 0 1 0 how did we get 0 in the first row first column, we
> > > should only alter the last row and column, right?
> > > 1 1 1
> > > 0 1 0
>
> > > After second scan:
> > > 0 0 0 how did we get these zero, only columns are to be
> > > changed, right?
> > > 0 1 1
> > > 0 0 0
>
> > > After third scan:
> > > 0 0 0
> > > 0 1 0 how did we get this as, ast element is ignored, right?
> > > 0 0 0
>
> > > Hope this helps.
> > > Dave
>
> > > On Nov 22, 9:34 am, "chandra kumar" <[EMAIL PROTECTED]>
> > > wrote:
> > > > Hi Dave,
> > > > Can you explain your algo for these 2 cases...
>
> > > > 0 1 1 1 1 0
> > > > 1 1 1 1 1 1
> > > > 1 1 1 0 1 1
>
> > > > Please explain me in steps cause we tried the same problem and
> can't
> > > get
> > > > it done for without using extra space. ( we used 1 extra space, if the
> > > > array can contain only 0 or 1 and no other number, otherwise we store
> > > some
> > > > other number indicating a yet to become zero and proceed, in the later
> > > case
> > > > we need no extra space )
> > > > Thanks and Regards,
> > > > K.V.Chandra Kumar
>
> > > > On 15/11/2007, Dave < <mailto:[EMAIL PROTECTED]> dave_and_da...
> @juno.com> wrote:
>
> > > > > Scan the array. If the i,j element is zero, set the last element of
> > > > > row i and the last element of column j to zero. Then, scan the last
> > > > > row, ignoring the last element, and zero every column that ends with
> a
> > > > > zero. Similarly, scan the last column, ignoring the last element,
> and
> > > > > zero every row that ends with a zero. This touches every element at
> > > > > most 3 times; i.e., if the array has m rows and n columns, the
> > > > > algorithm is O(1) in space and O(m*n) in time.
>
> > > > > Dave
>
> > > > > On Nov 14, 1:27 pm, geekko < [EMAIL PROTECTED]> wrote:
> > > > > > Given an array of 0's and 1's whenever you encounter an 0 make
> > > > > > corresponding column and row elements 0. How could you do that
> > > > > > efficiently(minimum time and minimum space complexity)? This
> > > question
> > > > > > is taken from placementsindia.blogspot.com- Hide quoted text -
>
> > > > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
