|
223. Find median of two sorted arrays.
Microsoft Interview Questions and Answers
(Continued from previous question...)
223. Find median of two sorted arrays.
Question:
Find median of two sorted arrays.
maybe an answer:
#include<stdio.h>
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(" i=%d j=%d\n",i,j);
if(j>0 &,& j<N &,& i<M &,& a[i]>b[j-1] &,& a[i]<b[j])
return a[i];
if(i>0 &,& i<M &,& j<N &,& b[j]>a[i-1] &,& b[j]<a[i])
return b[j];
if(j==0 &,& i<M &,& a[i]<b[j])
return a[i];
if(i==0 &,& j<N &,& b[j]<a[i])
return b[j];
if(j==N &,& a[i]>b[j-1])
return a[i];
if(i==M &,& b[j]>a[i-1])
return b[j];
if(i
{
if(a[i]<b[j])
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
else
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
}
else if(i>=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf("%d",findKthsmallest(a,m,b,n,k));
return 0;
}
(Continued on next question...)
Other Interview Questions
| 