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 this http://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.
