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 be nlogk.
another method with time complexity n+ klogn create a max heap tree of size n. O(n) keep on deleting the root node for k-1 operations by maintaining the heap property. Finally you will be left with the kth largest mode at the root. O(klogn) On Sat, Jan 14, 2012 at 7:58 PM, Ashish Goel <[email protected]> wrote: > 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 > "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. > -- 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.
