Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation.
-------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond <[email protected]>wrote: > nice solution appreciate it. but your algorithm is wasting time in finding > all the element... > instead of that just find boundary line kth element which can help as in > finding element greater that kth and element small than kth and that soluton > can be done in O(N) > > > On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY < > [email protected]> wrote: > >> >> 1) Construct max heap by taking first k elements in an array >> 2) if k+1 element less than root of max heap >> a) Delete root of max heap >> b) Insert k+1 element in max heap and apply heapify method >> 3) else skip the element >> 4) apply above procedure for all n elements in an array >> >> At last you will get k smallest elements and root is kth smallest element >> in the array >> >> this is O(nlogk) >> >> >> >> ---------------------------------------- >> CHERUVU JAANU REDDY >> M.Tech in CSIS >> >> >> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy <[email protected] >> > wrote: >> >>> Can any one tell how to do this when there are 'm' queries like "query i >>> j k" find the kth largest element in between indices i->j in an array. >>> When m is large even an O(n) algorithm would be slow. >>> I thinking that each query could be answered in O(sqrt(n)) time >>> So any suggestions ? >>> >>> Thanks >>> >>> >>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond <[email protected]>wrote: >>> >>>> there are better solution of O(n) are posted in the thread.......[?]. >>>> using order statices .... >>>> >>>> >>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur < >>>> [email protected]> wrote: >>>> >>>>> Create a temp array temp[0..k-1] of size k. >>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep updating the >>>>> smallest element of temp[] >>>>> 3) Return the smallest of temp[] >>>>> Time Complexity: O((n-k)*k). >>>>> >>>>> >>>>> try it ..............for this problem[?] >>>>> >>>>> -- >>>>> 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]<algogeeks%[email protected]> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> ~~~~BL/\CK_D!AMOND~~~~~~~~ >>>> >>>> -- >>>> 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]<algogeeks%[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]<algogeeks%[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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > -- > 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]<algogeeks%[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.
<<338.gif>>
<<361.gif>>
