Hello Venkat
One scenario that is troubling me is what if p2 is not a valid position in
l2?
findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] l2[p2]:
if l1[p1 + 1] l2[p2]:
return l2[p2]
else:
return findNth(p1+1, end)
else:
if l2[p2 + 1] l1[p1]:
Use a binary search.
If you have arrays a[n] and b[m], then if you claim that a[i] is the
kth largest element, then b[k-i-2] must be larger than a[i], and b[k-
i-1] must be less (assuming arrays are zero-based). After using a
binary search to find the value of i to meet this condition, you have
Hey Ashish check this link
http://stackoverflow.com/questions/8999610/median-of-lists
Thanks and Regards,
Venkat Gottipati
On Jan 31, 10:14 am, Ashish Goel ashg...@gmail.com wrote:
i think this can be done much faster similar to findling median of two
sorted arrays by proceeding with
@Atul: Yours is an O(k) algorithm. Is there an O(log k) solution?
Dave
On Jan 30, 9:56 pm, atul anand atul.87fri...@gmail.com wrote:
to find kth largest element in the 2 sorted array can be done by simple
merge...
obv no need for extra space...two indexes will do.
you just need to check
@dave:
checkout this link:-
http://www.geeksforgeeks.org/archives/2105
algo given in this link has complexity of O(log n) .btw i have doubt if
they would work if two array are of different size.
for O(log k) ...thinking
On Tue, Jan 31, 2012 at 11:06 AM, Dave dave_and_da...@juno.com wrote:
ya orderd statistics refer cormen book .It uses a slightly modified
version of quick sort.
On Jan 14, 8:01 pm, saurabh singh saurab...@gmail.com wrote:
nth order statistics http://en.wikipedia.org/wiki/Selection_algorithm
Saurabh Singh
B.Tech (Computer Science)
MNNIT
@Dave: TC in your first case will be O(klogn + n).
Transforming array into heap would be O(n).
Correct me If i am wrong.
--
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
why evaryone is thinking about heap...we can use selection algorithm
and find the n-k smallest element in that. this will take O(n) time
On Sep 10, 1:23 pm, Kunal Patil kp101...@gmail.com wrote:
@Dave: TC in your first case will be O(klogn + n).
Transforming array into heap would be O(n).
just look at the cormen's 9th chapter in 3rd edition..
randomized_select procedure is exactly suitable for this..
it is less complex than heapify procedures and all
actually it is of modification of quick sort and u guys ll appreciate that..
On Sat, Sep 10, 2011 at 3:12 PM, a.maiskar
@kunal.. +1
@dave ... for min heap.. read my statement again... kth largest would be
(n-k+1)th smallest...
@others ... randomized- partioning.. will not assure of finding an
element..in O(n)
for finding median ... we can be assure... that... O(n)..
proof given in the cormenn
@Praveen: I can think of two ways you might be using the heap:
1) You transform the unordered input array into a max heap. This is
O(n log n). Then, k times, you remove the top element. This is O(k log
n). The total is O((k+n) log n).
2) You form a min heap of the first k elements of the array.
@Praveen: No. Brijesh was correct. Inserting an element into a heap
with k elements is O(log k). This must be done n times, so O(n log k).
Dave
On Sep 8, 12:50 pm, praveen raj praveen0...@gmail.com wrote:
@brijesh...Tht would...be... O(klogn)
--
You received this message because you are
12 matches
Mail list logo
