/*
* @lc app=leetcode.cn id=4 lang=cpp
* @lcpr version=21917
*
* [4] 寻找两个正序数组的中位数
*/
// @lc code=start
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() == 0)
{
return (nums2[(nums2.size()-1)/2]/1.0f + nums2[nums2.size()/2]/1.0f)/2;
}
if (nums2.size() == 0)
{
return (nums1[(nums1.size()-1)/2]/1.0f + nums1[nums1.size()/2]/1.0f)/2;
}
bool bSingle = (nums1.size() + nums2.size())%2;
int mid = (nums1.size() + nums2.size())/2;
if (!bSingle)
mid -= 1;
int i=0,j=0;
int mid1, mid2;
while(i < nums1.size() && j < nums2.size())
{
if (nums1[i] > nums2[j])
{
if (bSingle)
{
if (i+j == mid)
return nums2[j];
}
else
{
if (i+j == mid)
mid1 = nums2[j];
else if (i+j == mid+1)
return (mid1+nums2[j])/2.0f;
}
j++;
}
else
{
if (bSingle)
{
if (i+j == mid)
return nums1[i];
}
else
{
if (i+j == mid)
mid1 = nums1[i];
else if (i+j == mid+1)
return (mid1+nums1[i])/2.0f;
}
i++;
}
}
if (i >= nums1.size())
{
for(; j < nums2.size(); j++)
{
if (bSingle)
{
if (i+j == mid)
return nums2[j];
}
else
{
if (i+j == mid)
mid1 = nums2[j];
else if (i+j == mid+1)
return (mid1+nums2[j])/2.0f;
}
}
}
if (j >= nums2.size())
{
for(; i < nums1.size(); i++)
{
if (bSingle)
{
if (i+j == mid)
return nums1[i];
}
else
{
if (i+j == mid)
mid1 = nums1[i];
else if (i+j == mid+1)
return (mid1+nums1[i])/2.0f;
}
}
}
return 0;
}
};
// @lc code=end
/*
// @lcpr case=start
// [1,3]\n[2]\n
// @lcpr case=end
// @lcpr case=start
// [1,2]\n[3,4]\n
// @lcpr case=end
*/