Unfortunately this isn't true. See the example I gave earlier: 1 2 3 2 4 5 3 4 6
Thje median is 3. 1 2 2 3 >3< 4 4 5 6 Niether one of the 3's lies on the diagonal. When you pick any element P on the diagonal, all you know is that anything to the right and downward is no less than P and everything to the left and upward is no greater. This leaves the upper right and lower left rectangles of the matrix unrelated to P. On Nov 5, 3:51 am, ankit agarwal <ankit.agarwal.n...@gmail.com> wrote: > Hi, > > I think the median will always lie on the diagonal > a[n][1] ---- a[1][n] > because the elements on the LHS making the upper triangle will > always be less than or equal to the elements on the diagonal > and the RHS, elements in the lower triangle will be greater than or > equal to them. > > so sort the diagonal and find the middle element, that will be the > median. > > Thanks > Ankit Agarwal > > On Nov 5, 1:29 am, Gene <gene.ress...@gmail.com> wrote: > > > > > Here's an idea. Say we pick any element P in the 2D array A and use > > it to fill in an N element array X as follows. > > > j = N; > > for i = 1 to N do > > while A(i, j) > P do > > j = j - 1; > > end; > > X(i) = j; > > end; > > > This algorithm needs O(N) time. > > > The elements of X split each row with respect to P. That is, for each > > i = 1 to N, > > > A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <= N. > > > Now the strategy is to create two length N arrays a = [0,0,...0]; and > > b = [N,N,...]. We'll maintain the invariant that a[i] < Median <= b[i] > > for some i. I.e, they "bracket" the median. > > > We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N - > > b(i) ). These tell us how many elements there are left and right of > > the bracket. > > > Now reduce the bracket as in binary search: Guess a value P, compute > > X. If L(X) >= R(X), set b = X else set a = X. > > > Keep guessing new P values in a way that ensures we reduce the number > > of elements between a and b by some fixed fraction. If we can do > > that, we'll get to 1 element in O(N log N) time. > > > The remaining problem is picking good P's. Certainly the first time is > > easy. Just take A(N/2, N/2). This has approximately (at least) N^2/4 > > elements larger than it and N^2/4 smaller due to the sorted rows and > > columns. This is what we need to get O(N log N) performance. > > > But after the first split, things get trickier. The area between a and > > b takes on the shape of a slash / /, so you can't just pick a P that > > moves a and b together by a fixed fraction of remaining elements. > > > Not to worry! You can quickly look up the (at most) N row medians in > > the bracket, i.e. > > > { A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N } > > > and use the well known O(N) median selection algorithm to get a median > > of this. This has the quality we want of being somewhere roughly in > > the middle half of the remaining elements. The logic is the same as > > the selection algorithm itself, but in our case the rows are pre- > > sorted. > > > In all, each partitioning step requires O(N), and a fixed fraction > > (about 1/2) of the elements will be eliminated from the bracket with > > each step. Thus O(log n) steps will be needed to bring the bracket to > > size 1 for an overall cost of O(N log N). > > > I don't doubt that there's a simpler way, but this one seems to work. > > Anyone see problems? > > > On Nov 3, 3:41 pm, sravanreddy001 <sravanreddy...@gmail.com> wrote: > > > > any better solution than O(N^2) in worst case? > > > How do we take advantage of sorting and find in O(N lg N)- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.