@dave : +1
On Wed, Aug 17, 2011 at 4:05 PM, Dave <dave_and_da...@juno.com> wrote:
> @Anika: You don't have to find the max and min elements of the entire
> array to find a row that doesn't contain either of them. If you scan 3
> rows, you will find a row that contains the max of those three rows,
> another that contains the min, and the remaining row will contain
> neither. Scanning the rest of the array would serve only to increase
> the maximum and decrease the minimum, but it wouldn't alter the fact
> that that remaining row doesn't contain either. Thus, we don't need to
> scan the rest of the matrix.
>
> Dave
>
> On Aug 16, 11:23 pm, Anika Jain <anika.jai...@gmail.com> wrote:
> > i didnt get it tht even if there are distinct elements how scanning sum
> > three lines return us the max n min elements? how will this scan whole
> > matrix for finding the max n min elements???
> >
> > On Wed, Aug 17, 2011 at 1:32 AM, priya ramesh <
> >
> >
> >
> > love.for.programm...@gmail.com> wrote:
> > > are these algos optimal???
> > > *Algo 1*:
> >
> > > no_min_max = -1
> > > min_row = max_row = -1
> > > for(i=0; i<n; i++)
> > > {
> > > for(j=0; j<n; j++){
> > > find min, max
> > > }
> > > if(min<prev_min && max > prev_max){
> > > no_min_max=i;
> > > break;
> > > }
> > > else if(min < prev_min){
> > > min_row=i;
> > > }
> > > else if(max>prev_max){
> > > max_row=i;
> > > }
> > > }
> > > if(no_min_max!=-1){
> > > i=0;
> > > while(i!=min_row && i!=max_row)
> > > i++;
> > > no_min_max=i;
> > > }
> >
> > > print no_min_max row;
> >
> > > *Algo 2:*
> >
> > > 1. Copy elements into a linear array
> >
> > > 2. Find min and max. O(n)
> >
> > > 3. for(i=0; i<rows; i++){
> >
> > > serach for min, max in the ith row; O(n)
> > > if (both not found)
> > > break;
> > > }
> >
> > > print the ith row;
> >
> > > Which 1 is better???
> >
> > > --
> > > 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
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> 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
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
