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
<akshatasharm...@gmail.com>wrote:
> @Anantha
> can you explain the logic please?
> On Fri, Jun 24, 2011 at 10:21 PM, Anantha Krishnan <
> ananthakrishnan....@gmail.com> 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 <ankurseth...@gmail.com>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 algogeeks@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.
>>>
>>>
>> --
>> 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.
>> 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.
> 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
