Actually, this might not always be the best approach. Example:
-1 1 2 3 4
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2*N = 10 steps.
With my algo, you'll go:
Step 1: top-left: negative, count++,
Step2: [0][1] non negative, set limitRow=0 (or 1 depending on how you
code)
Step3: for([i][j] < limitRow)
check [1] [0]: non negative, set limitColumn = 0;
since i=limitRow, j=limitCol, stop; count =1.
> We can do it in O(n * log n) by individually binary-searching for zero on
> each of the rows. Once we get the index of the first position where zero
> appears, counting the number of negative number is straight-forward.
What if there are no zero elements at all?
-Minotauraus.
> Here is an even better O(N) algorithm which is very elegant:
> Consider the bottom-left element of the given 2-D array.
> If it is negative, the whole of first-column is negative. So we can add
> that count and ignore that column from then onwards.
> If it is non-negative, the whole of last-row is non-negative. So we can
> ignore that row without changing the count.
> Therefore, by just doing one comparison we are able to "eliminate" one row
> or one column.
> We can iteratively follow this approach and it will terminate in exactly 2*N
> steps.
--
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?hl=en.
