Find the kth element using order statistics - O(n) <> As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine..
-------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta <souri.isthe...@gmail.com>wrote: > Steps: > 1. Find the kth element using order statistics - O(n) > 2. In one pass over the array, get all the elems less than the kth element. > > Let me know if this is not correct. > > > > On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com > > wrote: > >> I have already given an O(n) solution. See above ! >> >> The BST solution is O(nlogn) but is practically more nice. :) >> >> -------------------------------------------------- >> 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, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal < >> nikhil.bhoja...@gmail.com> wrote: >> >>> >>> >>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> wrote: >>> >>>> are yaar... i meant BST... i thought that was obvious ! >>>> sry if i confused you.... >>>> >>> >>> @rohit It's ok.Actually in this group people come up with very different >>> and non-common solutions so its risky to take things 'obviously'. >>> Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) >>> [for rotating n times]=O(nlogn) . >>> >>> Till now best algo we have is using heaps which give rise to complexity = >>> O(n+klogn) >>> >>> Please pass on algos having better runtime 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, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal < >>>> nikhil.bhoja...@gmail.com> wrote: >>>> >>>>> Hey rohit.You were referring to Binary tree.Search keyword was >>>>> missing.Because rotation makes no sense in binary tree.Please note binary >>>>> tree and BST are different. >>>>> >>>>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf < >>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>> >>>>>> Read the slides i uploaded. They explain what rotation does in a BST. >>>>>> >>>>>> Also you might like to refer to Red Black Trees in CLRS.... that >>>>>> chapter explains rotations. >>>>>> >>>>>> -------------------------------------------------- >>>>>> 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, Apr 12, 2010 at 8:18 AM, Rohit Saraf < >>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>> >>>>>>> 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 <nikhil.bhoja...@gmail.com> wrote: >>>>>>> > >>>>>>> > >>>>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>>>>>> rohit.kumar.sa...@gmail.com> >>>>>>> > 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>> >> >>>>>>> >> >>>>>>> >> 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 algogeeks@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<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>> . >>>>>>> >> 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 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. >>>>>>> > >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> >>>>>>> -------------------------------------------------- >>>>>>> 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> >>>>>>> >>>>>> >>>>>> -- >>>>>> 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 >>>>> 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 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 >>> 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 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. > -- 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>>
