solution.md

# 寻找两个正序数组的中位数

<p>给定两个大小分别为 <code>m</code> 和 <code>n</code> 的正序（从小到大）数组 <code>nums1</code> 和 <code>nums2</code>。请你找出并返回这两个正序数组的 <strong>中位数</strong> 。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums1 = [1,3], nums2 = [2]<strong><br />输出：</strong>2.00000<strong><br />解释：</strong>合并数组 = [1,2,3] ，中位数 2</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums1 = [1,2], nums2 = [3,4]<strong><br />输出：</strong>2.50000<strong><br />解释：</strong>合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>nums1 = [0,0], nums2 = [0,0]<strong><br />输出：</strong>0.00000</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>nums1 = [], nums2 = [1]<strong><br />输出：</strong>1.00000</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>nums1 = [2], nums2 = []<strong><br />输出：</strong>2.00000</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>nums1.length == m</code></li>	<li><code>nums2.length == n</code></li>	<li><code>0 <= m <= 1000</code></li>	<li><code>0 <= n <= 1000</code></li>	<li><code>1 <= m + n <= 2000</code></li>	<li><code>-10<sup>6</sup> <= nums1[i], nums2[i] <= 10<sup>6</sup></code></li></ul><p> </p><p><strong>进阶：</strong>你能设计一个时间复杂度为 <code>O(log (m+n))</code> 的算法解决此问题吗？</p>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
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<int> nums1(arr1, arr1 + length1);
    vector<int> 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<int> nums1, vector<int> 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<int> &nums1, vector<int> &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<int> &nums1, vector<int> &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<int> &nums1, int i, vector<int> &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<int> &nums1, vector<int> &nums2)
    {
        vector<int> 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<int> &nums1, vector<int> &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;
    }
};
```