# 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution test;
float ret;
int arr1[] = {1, 2};
int arr2[] = {3, 4};
int length1 = sizeof(arr1) / sizeof(arr1[0]);
int length2 = sizeof(arr2) / sizeof(arr2[0]);
vector nums1(arr1, arr1 + length1);
vector nums2(arr2, arr2 + length2);
ret = test.findMedianSortedArrays(nums1, nums2);
cout << setiosflags(ios::fixed) << setprecision(5) << ret << endl;
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
int getK(vector nums1, vector nums2, int k)
{
int len1 = nums1.size();
int len2 = nums2.size();
int index1 = 0, index2 = 0;
while (1)
{
if (index1 == len1)
{
return nums2[index2 + k - 1];
}
if (index2 == len2)
{
return nums1[index1 + k - 1];
}
if (k == 1)
{
return max(nums1[index1], nums2[index2]);
}
int newIndex1 = max(index1 + k / 2 - 1, len1 - 1);
int newIndex2 = max(index2 + k / 2 - 1, len2 - 1);
if (nums1[newIndex1] <= nums2[newIndex2])
{
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else
{
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector &nums1, vector &nums2)
{
int wholeLen = nums1.size() + nums2.size();
if (wholeLen % 2 == 0)
{
return (getK(nums1, nums2, wholeLen / 2) + getK(nums1, nums2, wholeLen / 2 + 1)) / 2.0;
}
else
{
return getK(nums1, nums2, wholeLen / 2 + 1);
}
}
};
```
## 选项
### A
```cpp
class Solution
{
int len1;
int len2;
public:
double findMedianSortedArrays(vector &nums1, vector &nums2)
{
if (nums1.size() <= 0 && nums2.size() <= 0)
return 0;
len1 = nums1.size();
len2 = nums2.size();
int left = (len1 + len2 + 1) / 2, right = (len1 + len2 + 2) / 2;
return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0;
}
int find(vector &nums1, int i, vector &nums2, int j, int k)
{
if (i >= nums1.size())
return nums2[j + k - 1];
if (j >= nums2.size())
return nums1[i + k - 1];
if (k == 1)
return min(nums1[i], nums2[j]);
int midval1 = i + k / 2 - 1 < nums1.size() ? nums1[i + k / 2 - 1] : INT_MAX;
int midval2 = j + k / 2 - 1 < nums2.size() ? nums2[j + k / 2 - 1] : INT_MAX;
if (midval1 < midval2)
return find(nums1, i + k / 2, nums2, j, k - k / 2);
else
return find(nums1, i, nums2, j + k / 2, k - k / 2);
}
};
```
### B
```cpp
class Solution
{
public:
double findMedianSortedArrays(vector &nums1, vector &nums2)
{
vector vecSumArr(nums1.size() + nums2.size());
merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), vecSumArr.begin());
if (vecSumArr.size() % 2 == 0)
return (*(vecSumArr.begin() + vecSumArr.size() / 2 - 1) + *(vecSumArr.begin() + vecSumArr.size() / 2)) * 1.0 / 2;
else
return *(vecSumArr.begin() + vecSumArr.size() / 2);
}
};
```
### C
```cpp
class Solution
{
public:
double findMedianSortedArrays(vector &nums1, vector &nums2)
{
int nums1Size = nums1.size();
int nums2Size = nums2.size();
int na = nums1Size + nums2Size;
int *ns = (int *)malloc(4 * na);
int i = 0, j = 0, d = 0;
int m = na / 2 + 1;
while (d < m)
{
int n;
if (i < nums1Size && j < nums2Size)
{
n = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
}
else if (i < nums1Size)
{
n = nums1[i++];
}
else if (j < nums2Size)
{
n = nums2[j++];
}
ns[d++] = n;
}
if (na % 2)
{
return ns[d - 1];
}
return (ns[d - 1] + ns[d - 2]) / 2.0;
}
};
```