@Arun..
If the no. of elements are odd then the median would be the middle
element... But, diff would be 0.
In case of even elements diff is either -1 or 1.
To prove the above,
Say currently diff is -1. and say maxH has X elements. That means minH
has X+1 elements.
Hence the total no. of
@lucifer: can you explain to me in the current median calculation why if
there is a Diff =1 or -1 you are using M and top(maxh) or M and top(minh)
for median calculation. If the number of elements from the stream so far is
odd then median is just one element and not average of 2 elements right?
http://www.geeksforgeeks.org/archives/14873
On Mon, Dec 19, 2011 at 12:17 PM, WgpShashank shashank7andr...@gmail.comwrote:
@lucifier thought to post the same post , saw the post little bit late .
though other approaches exist ,its the most efficient till we have.
nice job :)
Thanks
@lucifier thought to post the same post , saw the post little bit late .
though other approaches exist ,its the most efficient till we have.
nice job :)
Thanks
Shashank
CSE, BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
I guess median would be the middle element of the array(A[n/2]) where
n is odd, and if the array size is even then you might return the mean
of two middle values.
On Dec 16, 12:26 pm, Sangeeta sangeeta15...@gmail.com wrote:
You are given a stream of numbers which can be positive or negative.
If the input stream does not allows random access(and we cant store the
elements in auxillary memory) then there is no way to find in O(1)(Can be
done non-deterministically though in O(1)) .
If the above two constraints are not present then the problem is trivial
enough to be discussed.
On Fri,
@sangeeta
I think your question is, given an input stream of nos., at any random
time, we need to find what's the current median.
For eg- say 4 nos have been read till now, hence, whats the median in
those 4 nos. Say now, 7 nos have been read till now from the stream so
which is the current
