but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp
On 4/11/10, Nikhil Agarwal <[email protected]> wrote: > > > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf <[email protected]> > wrote: >> >> Time complexity is O(n log n). But the last solution I gave has O(n). >> >> What did u not understand abt thesolution > > > @Rohit Please explain how that Binary tree solution works. >> >> >> -------------------------------------------------- >> 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 >> <[email protected]> wrote: >>> >>> >>> >>> On 11 April 2010 10:46, Rohit Saraf <[email protected]> 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 >>>> >>>> >>>> >>>> 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]. >>>>>>>>> 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]. >>>>>>>> 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. >>>>>> >>>>>> >>>>>> -- >>>>>> 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. >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> ~~~~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]. >>>>> 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. >>> >>> >>> >>> >>> -- >>> 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 [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. > > > > > -- > Thanks & Regards > Nikhil Agarwal > Junior Undergraduate > Computer Science & Engineering, > National Institute Of Technology, Durgapur,India > http://tech-nikk.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 [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. > -- -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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>>
