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 <[email protected]> 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 <[email protected]> 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) -- 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.
