首页 > 代码库 > 第三周 leetcode 4. Median of Two Sorted Arrays (HARD)
第三周 leetcode 4. Median of Two Sorted Arrays (HARD)
4. Median of Two Sorted Arrays
给定两个有序的整数序列。求中位数，要求复杂度为对数级别。
通常的思路，我们二分搜索中位数，对某个序列里的某个数 我们可以在对数时间内通过二分算法求得两个序列中比它小的数，整体复杂度也是对数级别。但是代码实现较为困难。
换一个思路，我们把中位数不要当作一个数，而当作一个序列的划分。划分后，序列的左半部设为L，右半部设为R 满足max(L)<=min(R)且满足len(L)==len(R)
二分搜索这个划分即可。对于A+B的长度为奇数的情况，我们进行特殊处理，在划分时允许“借一位”。
其中一个序列为空则直接输出答案。
补充一个算法，对于两个无序的数列求中位数，《算法概论》中给出了线性的解法。通过类似快速排序的划分方法对数列进行划分，预测中位数可能存在的部分。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums2.size()==0)
{
if(nums1.size()%2==0)return (double)(nums1[nums1.size()/2]+nums1[nums1.size()/2-1])/2.0;
else return (double)nums1[nums1.size()/2];
}
if(nums1.size()==0)
{
if(nums2.size()%2==0)return (double)(nums2[nums2.size()/2]+nums2[nums2.size()/2-1])/2.0;
else return (double)nums2[nums2.size()/2];
}
int len=(nums1.size()+nums2.size())/2;
bool flag=(nums1.size()+nums2.size())%2==1;
if(flag)len++;
int l=-1,r=min((int)nums1.size()-1,len-1);
while(true)
{
int i=(l+r)/2,ii;
ii=i+1;
int j=len-(i+1)-1,jj;
jj=j+1;
if(j>=(int)nums2.size()){l=i+1;continue;}
int l1=-2147483647,l2=-2147483647,r1=2147483647,r2=2147483647;
if(i>=0)l1=nums1[i];
if(j>=0)l2=nums2[j];
if(ii<nums1.size())r1=nums1[ii];
if(jj<nums2.size()) r2=nums2[jj];
if(flag&&l1>=l2)r1=min(l1,r1);
if(flag&&l2>l1)r2=min(r2,l2);
int maxa=max(l1,l2);int minb=min(r1,r2);
if(maxa<=minb){return (double)(maxa+minb)/2.0;}
if(l1>r2){r=i-1;continue;}
else{l=i+1;continue;}
}
}
};
第三周 leetcode 4. Median of Two Sorted Arrays (HARD)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。