My solution is ::::
take thousand elements and store in linked list in ascending order
store the addresses of nodes in an array
take 1001th element
binary search on array [ take ele using the address ]
find the position of that..and insert that node
delete last node
like this do the thing
space complexity is low
before doing binary search first compare wid last element
it improves the performance
On 7/27/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
This is how i think it could be done: (assuming you know the range of
elements)
- Divide the whole range of elements into sub ranges.
- Iterate through all the arrays and get the no. of elements in each
range.
- From this you can get a subrange of elements in which your median
would fall.
- From each array extract the elements which fall in that range.
- Now do a merge on the extracted arrays till you get the ith element,
where i = k - no.of elements before this subrange.
The advantage of this method is that a lot of computation can be done
on the client side and very little data needs to be transfered across
machines. The complexity of this algo is O(n).
Is there a O(log N) algo for this? The algo's proposed look O(N log 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
-~----------~----~----~----~------~----~------~--~---
