Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution
-------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee <dona.1...@gmail.com>wrote: > > > On 11 April 2010 10:46, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote: > >> 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. >> Please prove the correctness of your algorithm with the time complexity >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond <patidarc...@gmail.com>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 < >>> jaanu.cher...@gmail.com> 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 < >>>> abhijith200...@gmail.com> 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 >>>>> <patidarc...@gmail.com>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 < >>>>>> mukeshraj8...@gmail.com> 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 algoge...@googlegroups.com. >>>>>>> To unsubscribe from this group, send email to >>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>> . >>>>>>> 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 algoge...@googlegroups.com. >>>>>> To unsubscribe from this group, send email to >>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>> . >>>>>> 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 algoge...@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> 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 algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks & Regards, > Priyanka Chatterjee > Third Year Undergraduate Student, > Computer Science & Engineering, > National Institute Of Technology,Durgapur > India > http://priyanka-nit.blogspot.com/ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<338.gif>>
<<361.gif>>
