Median of Two Sorted Arrays
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)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution 1:
int len1 = nums1.size();
int len2 = nums2.size();
vector<int> list;
//每次都从nums1和nums2中找小的push_back进去，
//直到vector的size 为 (len1+len2)/2;
if((len1+len2)%2==0)
{
return list[ (len1+len2)/2];
}
else
{
return (list[ (len1+len2)/2]+ list[ (len1+len2)/2-1])/2.0;
}
//缺点：申请了新的内存，时间是(m+n)/2 不是long(m+n)
//但是时间效果比使用二分查找速度快
Solution 2:
//开辟新的空间，寻找中位数，实际上和上面思路基本相同
//缺点：时间复杂度不是log(m+n)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int num1 = nums1.size();
int num2 = nums2.size();
if(num1 == 0 && num2 == 0)
return 0.0;
int total = num1 + num2;
int mid = total / 2;
int flag = total % 2;
int left1 = 0;
int left2 = 0;
int count = 0;
if(flag == 0)
{
int res = 0;
while(count < mid)
{
if(left1<num1 && left2<num2)
{
if(nums1[left1]<nums2[left2])
{
res = nums1[left1];
left1++;
count++;
}
else
{
res = nums2[left2];
left2++;
count++;
}
}
else if(left1<num1 && left2==num2)
{
res = nums1[left1];
left1++;
count++;
}
else if(left1==num1 && left2<num2)
{
res = nums2[left2];
left2++;
count++;
}
}
int res2 = 0;
if(left1<num1 && left2<num2)
{
if(nums1[left1]<nums2[left2])
{
res2 = nums1[left1];
}
else if(nums1[left1]>nums2[left2])
{
res2 = nums2[left2];
}
else
{
res2 = nums1[left1];
}
}
else if(left1<num1 && left2==num2)
{
res2 = nums1[left1];
}
else if(left1==num1 && left2<num2)
{
res2 = nums2[left2];
}
double result = (res2 + res)/2.0;
return result;
}
else
{
int median = mid;
int res = 0;
while(count <= mid)
{
if(left1<num1 && left2<num2)
{
if(nums1[left1]<nums2[left2])
{
res = nums1[left1];
left1++;
count++;
}
else
{
res = nums2[left2];
left2++;
count++;
}
}
else if(left1<num1 && left2==num2)
{
res = nums1[left1];
left1++;
count++;
}
else if(left1==num1 && left2<num2)
{
res = nums2[left2];
left2++;
count++;
}
}
double result = res * 1.0;
return result;
}
return 0;
}
};
Solution 3:
//题目中明确要求时间复杂度为log(m+n)
//搜索时应该使用二分方法进行搜索
//常见的二分法是针对一个数组设置left和right标志，进算mid位与目标值大小关系来确定left和right的新值
//数组nums1的长度为m，nums2的长度为n
//假设存在i和j,i在[0,m-1]范围内,j在[0,n-1]范围内
//能使得nums1[0]~nums1[i-1]和nums2[0]~num2[j-1]恰好在中位左侧
//nums1[i]~nums1[m-1]和nums2[j]~nums2[j-1]恰好在中位右侧
//那么 i+j = m - i + j-i 或 i+j = m-i+n-j+1
//可以得到 i+j = (m+n+1)/2
//如果 i 属于[0,m-1] 那么 j = (m+n+1)/2 - i
//如果m>n 则 j可能是负数，因此这种情况下，我们交换nums1和nums2即可
//则问题就变成了找到合适的i,j使得nums2[j-1]<=nums1[i]并且nums1[i-1]<=nums2[j],由于可以由i计算j那么在[0,m-1]中寻找i即可，可以使用二分法查找
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if(m>n)
{
return findMedianSortedArrays(nums2,nums1);
}
int left = 0;
int right = m;
int mid = (m+n+1)/2;
while(left<=right)
{
int i = (left+right)/2;
int j = mid - i;
if(i<right&&nums2[j-1]>nums1[i])
{
left = i+1;
}
else if(i>left&&nums1[i-1]>nums2[j])
{
right = i-1;
}
else
{
int maxleft = 0;
if(i==0)
{
maxleft=nums2[j-1];
}
else if(j==0)
{
maxleft=nums1[i-1];
}
else
{
if(nums2[j-1]>nums1[i-1])
{
maxleft=nums2[j-1];
}
else
{
maxleft=nums1[i-1];
}
}
if((m+n)%2==1)
{
return maxleft;
}
int minright = 0;
if(i==m)
{
minright=nums2[j];
}
else if(j==n)
{
minright=nums1[i];
}
else
{
if(nums2[j]>nums1[i])
{
minright=nums1[i];
}
else
{
minright=nums2[j];
}
}
return (maxleft+minright)/2.0;
}
}
return 0.0;
}
网友评论