@Jitendra: where r u using k in the first call? On Jun 30, 8:56 am, Jitendra singh <[email protected]> wrote: > kthlargest(a[],b[],lefta,righta,leftb,rightb,k) > { > mida=lefta+(righta-lefta)/2; > midb=leftb+(rightb-leftb)/2; > if(a[mida]<bmidb]) > kthlargest(a[],b[],mida+1,righta,leftb,midb-1); > elseif(a[mida]>bmidb]) > kthlargest(a[],b[],lefta,mida-1,midb+1,rightb,); > else > return a[mida]; > > } > > On 6/25/11, Anantha Krishnan <[email protected]> wrote: > > > > > > > > > Idea is like this since both the arrays may not be of same length lets > > divide (k-1) smallest elements proportionally in both the arrays: > > > let i point the array A by > > i=m/(m+n) * (k-1) [since we have to divide k-1 elements among two] > > j=(k-1) - i > > > then try to insert A[i] between B[j-1] and B[j] if three are not in asc > > order try to insert B[j] between A[i-1] and A[i] > > If any one of the above satisfies we found kth smallest element else, > > > check which one is smallest among A[i] and B[j] its logical that if A[i] is > > smallest then we can A[0] to A[i] for the next iteration and > > k becomes k-i-1 also m becomes m-i-1 i.e now we have only m-i-1+n elements > > out of which we have to find k-i-1th smallest thus the iteration goes > > on until we > > find our kth smallest element. > > > Consider 2 arrays > > > A={5,7,9,20}; length of A: m=4 > > B={10,12,21,27,35,50}; length of B: n=6 > > > let K be 4 > > > i=4/10*3=1; A[1]=7; > > j=3-1=2; B[2]=21; > > > B[1]=12 A[1]=7 B[2]=21 [not in asc order] > > A[0]=5 B[2]=21 A[1]=7 [not in asc order] > > > so now, > > k=k-i-1 =4-1-1=2 > > m=m-i-1=4-1-1=2 > > n=6 > > > A={9,20}; length of A: m=2 > > B={10,12,21,27,35,50}; length of B: n=6 > > > i=2/8*1=0; A[0]=9; > > j=1-0=1; B[1]=12; > > > (acutally A[-1] is just for understanding) > > B[0]=10 A[0]=9 B[1]=12 [not in asc order] > > A[-1]=-INF B[1]=12 A[0]=9 [not in asc order] > > > now, > > k=k-i-1=2-0-1=1; > > m=m-i-1=2-0-1=1; > > n=6; > > A={20}; length of A: m=1 > > B={10,12,21,27,35,50}; length of B: n=6 > > > i=1/7*0=0; A[0]=20; > > j=0-0=0; B[0]=10; > > > (acutally A[-1] and B[-1] are just for understanding) > > B[-1]=-INF A[0]=20 B[0]=10 [not in asc order] > > A[-1]=-INF B[0]=10 A[0]=20 [in asc order] > > > We got the Kth(4th) smallest element which is 10. > > > Thanks & Regards, > > Anantha Krishnan > > > On Fri, Jun 24, 2011 at 11:20 PM, Akshata Sharma > > <[email protected]>wrote: > > >> @Anantha > >> can you explain the logic please? > >> On Fri, Jun 24, 2011 at 10:21 PM, Anantha Krishnan < > >> [email protected]> wrote: > > >>> Check thishttp://ideone.com/C8fQC > > >>> <http://ideone.com/C8fQC>Thanks & Regards, > >>> Anantha Krishnan > > >>> On Fri, Jun 24, 2011 at 10:18 PM, Decipher <[email protected]>wrote: > > >>>> Can anybody please explain how to solve this question with logarithmic > >>>> time complexity ? > > >>>> Write the code/algorithm to find the k-th Smallest Element in the > >>>> Union of Two Sorted Arrays . > > >>>> -- > >>>> 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. > > > -- > > 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.
