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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<338.gif>>
<<361.gif>>
