4. Median of Two Sorted Arrays
题目
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
题意是给出两个有序的列表，找出它们合并之后的中位数（如果个数为偶数，则是两个中位数的平均数）。
时间复杂度要求是O（log(m+n)）
解题思路
由于这题有时间复杂度要求，可以发现将两个列表合并成新列表再使用二分查找是不可行的。（时间复杂度为O（m+n）
所以这题我也是看了题解才有了思路。
由于两个列表 各自是有序的，我们可以考虑通过切割列表来寻找中位数。考虑同时切割列表，一个切割点为i，一个切割点为j，切割会把 列表分为[0, i), [i, n) ,[0, j), [j, m) 四个子列表，如果能满足以下条件，则我们可以快速找到中位数：
1）i+j = (m+n)/2
2）a[i-1] <= b[j]
3）b[j-1] <= a[i]
这样我们可以快速找到中位数为:
奇数情况下为：
min(a[i], b[j])
偶数情况下为：
(min(a[i], b[j]) + max(a[i-1], b[j - 1]))/2
示例代码
class Solution {
public:
int min(int a, int b){
return a < b ? a: b;
}
int max(int a, int b){
return a > b ? a: b;
}
int minelement(int indexa, int indexb, vector<int>& nums1 , vector<int>& nums2){
if(indexa == nums1.size()){
return nums2[indexb];
}
if(indexb == nums2.size()){
return nums1[indexa];
}
return min(nums1[indexa], nums2[indexb]);
}
int maxelement(int indexa, int indexb, vector<int>& nums1 , vector<int>& nums2){
if(indexa == nums1.size()){
return nums2[indexb];
}
if(indexb == nums2.size()){
return nums1[indexa];
}
return max(nums1[indexa], nums2[indexb]);
}
int next(int temp, int tl, int tr){
if(tl +1 == tr ){
if(temp == tl){
return tr;
}else{
return tl;
}
}
return (tl + tr) /2;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size();
int l2 = nums2.size();
int l = l1 + l2;
int mid = l / 2;
int temp, temp2 = 0;
if(l1 < l2){
nums1.swap(nums2);
l1 = nums1.size();
l2 = nums2.size();
}
if(l2 == 0){
if(l1 % 2 == 0){
return (double) (nums1[l1 / 2] + nums1[l1 / 2 - 1]) /2;
}else{
return (double) nums1[l1 / 2];
}
}
int tl = 0, tr = l1;
temp = (tl + tr) / 2;
while(true){
temp2 = mid - temp;
if(temp > mid){
tr = temp;
temp = next(temp, tl, tr);
continue;
}
if(temp2 > l2){
tl = temp;
temp = next(temp, tl, tr);
continue;
}
if(temp2 == 0){
if(nums1[temp - 1] <= nums2[0]){
break;
}else{
tr = temp;
temp = next(temp, tl, tr);
continue;
}
}else if(temp2 == l2){
if(nums2[temp2 - 1] <= nums1[temp]){
break;
}else{
tl = temp;
temp = next(temp, tl, tr);
continue;
}
}else{
if(nums1[temp - 1] <= nums2[temp2] && nums2[temp2 - 1] <= nums1[temp]){
break;
}else if(nums1[temp - 1] > nums2[temp2]){
tr = temp;
temp = next(temp, tl, tr);
continue;
}else{
tl = temp;
temp = next(temp, tl, tr);
continue;
}
}
}
if( l % 2 == 0){
int s;
if(temp2 == 0){
s = nums1[temp - 1] + minelement(temp, 0, nums1, nums2);
}else if(temp2 == l2){
s = maxelement(temp - 1, l2 - 1, nums1, nums2) + nums1[temp];
}else{
s = maxelement(temp - 1, temp2 - 1, nums1, nums2) + minelement(temp, temp2, nums1, nums2);
}
return (double)s / 2;
}else{
if(temp2 == 0){
return (double) minelement(temp,0, nums1, nums2);
}else if(temp2 == l2){
return (double) nums1[temp];
}else{
return (double) minelement(temp, temp2, nums1, nums2);
}
}
}
};
注意细节
- 注意i和j为0或者列表长度的时候（这里的corner case很多）
