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
_____
发件人: [email protected] [mailto:[EMAIL PROTECTED] 代表
chandra kumar
发送时间: 2007年11月23日 21:58
收件人: [email protected]
主题: [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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
