Hi,
I am trying to write code for this problem but having issues.
Can you help
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
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 arr1[i...n] == arr2[j..m]
if(arr1[i] arr2[j])
{
cnt++;
index=arr2[j];
j++;
}
else
{
cnt++;
index=arr1[i];
i think this can be done much faster similar to findling median of two
sorted arrays by proceeding with comparing medians of two arrays and then
reducing the data set to approx 3/4th of 2n. I am looking for that algo if
osmeone have.
Best Regards
Ashish Goel
Think positive and find fuel in
Hi,
how can we do so in O(n)
forming a heap or a tree with each node keeping children in its left node
still is nlogn
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
you can do it in nlogk or n+klogn time.
create a min-heap tree of size k with first k nodes.
Add k+1..n nodes in the tree. Everytime you insert a node in the tree check
if it's greater than the root node. If yes remove
root node and insert the new node (logk operations). So time complexity
will
nth order statistics http://en.wikipedia.org/wiki/Selection_algorithm
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sat, Jan 14, 2012 at 8:23 PM, Piyush Grover piyush4u.iit...@gmail.comwrote:
you can do it in nlogk or n+klogn time.
create a min-heap
How to find out Kth largest element in an array ?
--
Thanks Regards :
ROHIT JALAN
--
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
use max heap ,it will take n + k*logn
On Thu, Sep 8, 2011 at 10:25 PM, Rohit jalan jalanha...@gmail.com wrote:
How to find out Kth largest element in an array ?
--
Thanks Regards :
ROHIT JALAN
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Use the Randomized partition approach of quicksort to find the kth largest
element in the array.
With regards,
Praveen Raj
--
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
make a max heap of size K , and keep inserting all the elements in it.. and
at last the root will be the k-th largest element ! O(nlogk)
On Thursday, 8 September 2011 22:32:52 UTC+5:30, Sandeep Chugh wrote:
wat abt creating a max heap? and then deleting root element k-1 times..
after then
@Brijesh: Can you help me with a code ? or atleast pseudo code ? How are
you going to keep on inserting the elements ?
Thanks Regards,
-Rohit
On Thu, Sep 8, 2011 at 10:38 PM, Brijesh brijeshupadhyay...@gmail.comwrote:
make a max heap of size K , and keep inserting all the elements in it..
@brijesh...Tht would...be... O(klogn)
--
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.
Okay. We can do it with min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the
given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it
with root of MH.
a) If the element is greater than the root then make it root and call heapify
I am considering..
Maxheapify... A[parent(i)]=A[i]
kth largest element...
therefore O(klogn)...
k times u have to extract the largest element and logn to maintain the
maxheapify everytime.
minheapifyA[parent(i)]=A[i]
kth largest element that means ... (n-k) smallest element.
14 matches
Mail list logo
