4. Median of Two Sorted Arrays

----------------------------------------------------------------------------

Mean:

给定两个数组，求这两个数组的中位数.(要求时间复杂度为O(log(n+m))

analyse:

一开始用归并为一个数组的方法做了一下也AC了，看来lc的时间还是给的很宽的.

将本题转化为求第k大数就简单多了，其中求第k大数使用类似二分的方法来实现，从而将时间复杂度降到O(log(n+m)).

Time complexity: O(log(n+m)

view code

/**
 * -----------------------------------------------------------------
 * Copyright (c) 2016 crazyacking.All rights reserved.
 * -----------------------------------------------------------------
 *       Author: crazyacking
 *       Date  : 2016-02-03-12.07
 */
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using
namespace
std; 
typedef
long
long( 
LL); 
typedef
unsigned
long
long( 
ULL); 
const
double
eps( 
1e-8); 
/*Solution 1*/
class
Solution
{ 
//求A和B数组的第k大数
int
getMedian( 
int
A
[],
int
m
,
int B 
[],
int n 
,
int
k) 
{ 
if( 
m
>n) 
return
getMedian(B 
,n 
,
A
,
m
,
k); 
//默认A为短数组
if( 
m
==
0) 
return B 
[
k
-
1
];
if( 
k
==
1) 
return
min( 
A
[
0
], B 
[
0
]);
int
pa
=
min( 
k
/
2
,
m); 
int pb 
=
k
-
pa; 
if( 
A
[
pa
-
1
]
< B 
[pb 
-
1
])
{ 
return
getMedian( 
A
+
pa
,
m
-
pa
, B 
, n 
,
k
-
pa); 
}
else
if( 
A
[
pa
-
1
]
> B 
[pb 
-
1
])
{ 
return
getMedian( 
A
,
m
, B 
+pb 
, n 
-pb 
,
k
-pb); 
}
else
{ 
return
A
[
pa
-
1
];
}
return
0; 
}
public
:
double
work( 
int
A
[],
int
m
,
int B 
[],
int n) 
{ 
if(( 
m
+n) 
%
2
==
0) 
{ 
return ( 
getMedian( 
A
,
m
,B 
, n 
, ( 
m
+n) 
/
2) 
+
getMedian( 
A
,
m
,B 
, n 
, ( 
m
+n) 
/
2
+
1)) 
/
2.; 
}
else
{ 
return
getMedian( 
A
,
m
,B 
, n 
, ( 
m
+n) 
/
2
+
1); 
}
}
double
findMedianSortedArrays( 
vector
<
int
>&
nums1
,
vector
<
int
>&
nums2) 
{ 
int
A
[
10000
],B 
[
10000
];
int
idx
=
0; 
for( 
auto
p:
nums1) 
{ 
A
[
idx
++
]
=p; 
}
idx
=
0; 
for( 
auto
p:
nums2) 
{ 
            B 
[
idx
++
]
=p; 
}
int
m
=
nums1
.
size(); 
int n 
=
nums2
.
size(); 
double
ret
=
work( 
A
,
m
,B 
,n); 
return
ret; 
}
};
/*Solution 2*/
/*
class Solution
{ 
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    { 
        auto it1=nums1.begin();
        auto it2=nums2.begin();
        vector<int> a;
        while(it1!=nums1.end() || it2!=nums2.end())
        { 
            if(it1==nums1.end() && it2!=nums2.end())
            { 
                a.push_back((*it2));
                it2++;
            }
            else if(it1!=nums1.end() && it2==nums2.end())
            { 
                a.push_back(*it1);
                it1++;
            }
            else if(it1!=nums1.end() && it2!=nums2.end())
            { 
                if((*it1)<(*it2))
                { 
                    a.push_back(*it1);
                    it1++;
                }
                else
                { 
                    a.push_back(*it2);
                    it2++;
                }
            }
        }
        int len=a.size();
        double ans=(len%2)?(double)a[len/2]:(double)(a[len/2-1]+a[len/2])/2.;
        return ans;
    }
};
*/
int
main() 
{ 
int n 
,
m
,
temp; 
while( 
cin
>>n 
>>
m) 
{ 
vector
<
int
>
a
,b; 
for( 
int
i
=
0; 
i
<n; 
++
i) 
{ 
cin
>>
temp; 
a
.
push_back( 
temp); 
}
for( 
int
i
=
0; 
i
<
m; 
++
i) 
{ 
cin
>>
temp; 
              b 
.
push_back( 
temp); 
}
Solution
solution; 
double
ans
=
solution
.
findMedianSortedArrays( 
a
,b); 
cout
<<
"===========ans==========="
<<
endl; 
cout
<<
ans
<<
endl; 
}
return
0; 
}