Anika, what you are talking about is finding a specific element, not the kth largest or smallest element, can you give a walk through with an example in case i have understood you incorrectly
Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Thu, May 17, 2012 at 3:33 PM, Anika Jain <[email protected]> wrote: > there's a solution of O(log n) where 2D matrix has n rows and n columns. > Apply binary search for the search on the diagonal. when you are left with > just one element after the search apply binary search within that elements > row and its column. you will get the element. O(log n+log n+log n). so > O(log n). > > > On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri > <[email protected]>wrote: > >> Well I hv got Something running in my mind buy ofcse need some cornor >> case tuning. >> >> If we take sqrt() of the number (say K) than we can avoid looking into >> sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means >> that the final solution is possible in constant time (the time independent >> of k or matrix values), which ofcourse can go upto O(n) in worst case where >> N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of >> sqrt function to corner the value. >> >> Its seems okei logically to remove those rows and columns as we are >> certain that they are sorted in both ways and avoid unnecessary time >> looking for the place where it won't belong. >> >> Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)<k and >> now keep on adding the value to sqrt(k)+1 till U reach k and get corner >> that element. >> >> I guess it works.. >> >> >> >> On Wed, May 16, 2012 at 1:17 PM, Ashish Goel <[email protected]> wrote: >> >>> Vikas, can you suggest the logic of this also? I am a bit unclear on how >>> the 2D arr is being used as a heap and how recursion is used to solve this >>> >>> Best Regards >>> Ashish Goel >>> "Think positive and find fuel in failure" >>> +919985813081 >>> +919966006652 >>> >>> >>> >>> On Thu, Oct 13, 2011 at 11:37 PM, vikas <[email protected]>wrote: >>> >>>> @Sunny, good catch, k X k approach wont work >>>> >>>> lets try to use matrix itself as heap >>>> >>>> heapify(int cr, int cc, int Nr, int Nc){ >>>> mr = cr; mc = cc; >>>> if(cr+1 < Nr) >>>> mr = cr+1 mc = cc; >>>> if(cc + 1 < Nc && min > A[cc+1][cr]) >>>> mr = cr; mc = cc+1; >>>> if(A[cr][cc] > A[mr][mc]){ >>>> swap(&A[cr][cc] ,&A[mr][mc]); >>>> heapify(mr, mc, Nr, Nc); >>>> } >>>> >>>> extract_min(){ >>>> swap(&A[0][0], &A[hr][hc]); >>>> if(hc > 0) hc--; >>>> else if(hr > 0){ >>>> hr --; >>>> hc = N; >>>> } >>>> if(hr | hc) >>>> heapify(0, 0, hr, hc); >>>> } >>>> >>>> >>>> } >>>> >>>> >>>> On Oct 13, 12:18 pm, sunny agrawal <[email protected]> wrote: >>>> > Nopes >>>> > Still it does not ensure that duplicates will not be there in the >>>> priority >>>> > queue >>>> > >>>> > what i mean is you cannot write directly >>>> > >>>> > do k times{ >>>> > data = pop() >>>> > // let i,j are row and col of data >>>> > push(i+1,j); >>>> > push(i,j+1); >>>> > >>>> > } >>>> > >>>> > you need to add the following checks >>>> > >>>> > if((i+1,j) is not in the heap) push(i+1,j) >>>> > if((i,j+1) is not in the heap) push(i,j+1) >>>> > because heap does not automatically check for duplicates >>>> > >>>> > and to check for duplicates we need an extra data structure other >>>> than heap, >>>> > which stores that which (i+1,j) are already there in the heap map can >>>> also >>>> > be used so overall complexity will go O(k* lg^2K) >>>> > >>>> > On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra < >>>> [email protected]>wrote: >>>> > >>>> > >>>> > >>>> > > struct data >>>> > > { >>>> > > int row, col, >>>> > > int val; >>>> > > }; >>>> > >>>> > > priority_queue<data> heap; >>>> > >>>> > > now fine? >>>> > >>>> > > -- >>>> > > 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. >>>> > >>>> > -- >>>> > Sunny Aggrawal >>>> > B.Tech. V year,CSI >>>> > Indian Institute Of Technology,Roorkee >>>> >>>> -- >>>> 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. >> > > > > -- > Regards > Anika Jain > > -- > 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.
