There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
c++归并算法 v1.0 奇偶分开
class Solution
{
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int n1=nums1.size();
int n2=nums2.size();
int k=n1+n2;
int a[k];
int m=0,n=0;
if(k%2==1)
{
int i=0;
while(m<n1&&n<n2)
if(nums1[m]<=nums2[n])
{
a[i++]=nums1[m++];
}
else
{
a[i++]=nums2[n++];
}
while (m<n1)
{
a[i++]=nums1[m++];
if(i==k/2+1)
break;
}
while(n<n2)
{
a[i++]=nums2[n++];
if(i==k/2+1)
break;
}
return a[k/2];
}
else
{
int i=0;
while(m<n1&&n<n2)
if(nums1[m]<=nums2[n])
{
a[i++]=nums1[m++];//可能越界
}
else
{
a[i++]=nums2[n++];
}
while (m<n1)
{
a[i++]=nums1[m++];
if(i==k/2+1)
break;
}
while(n<n2)
{
a[i++]=nums2[n++];
if(i==k/2+1)
break;
}
return (a[k/2-1]+a[k/2])/2.0;
}
}
};
c++归并算法 v2.0 奇偶合并
class Solution
{
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int n1=nums1.size();
int n2=nums2.size();
int k=n1+n2;
int a[k];
int m=0,n=0;
int i=0;
while(m<n1&&n<n2)
if(nums1[m]<=nums2[n])
{
a[i++]=nums1[m++];//可能越界
}
else
{
a[i++]=nums2[n++];
}
while (m<n1)
{
a[i++]=nums1[m++];
if(i==k/2+1)
break;
}
while(n<n2)
{
a[i++]=nums2[n++];
if(i==k/2+1)
break;
}
return (a[(k-1)/2]+a[k/2])/2.0;
}
};
python
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n1=len(nums1)
n2=len(nums2)
num=n1+n2
m=0
n=0
i=0
ans=[]
while(m<n1 and n<n2):
if(nums1[m]<=nums2[n]):
ans.append(nums1[m])
m+=1
else:
ans.append(nums2[n])
n+=1
while(m<n1):
ans.append(nums1[m])
m+=1
while(n<n2):
ans.append(nums2[n])
n+=1
return (ans[(num-1)/2]+ans[num/2])/2.0
注意事项
1.原先想在最外层套用的是for循环，好在中途就退出减少使用时间，但是i并不容易控制，所以最后还是用了while循环，使得i的控制随心所欲
2.无论奇数偶数，使用(a[(k-1)/2]+a[k/2])/2.0都是一样的，数量为奇数的话都是本身，数量偶数的话就是中间前一个加后一个
3.最坏时间复杂度为O(m+n)，仍然没达到题目要求
