寻找两个正序数组的中位数---多种解法

寻找两个正序数组的中位数---多种解法 题意

给定两个大小分别为 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

数据范围

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-1e6 <= nums1[i], nums2[i] <= 1e6

中位数是排序后的数据，不要直接找中位数，我在这上面踩过坑

思路1---暴力

1.这个题暴力是能过的，可以先考虑暴力

2.先合并数组，再排序，然后输出奇偶不同状态下的值

代码

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector res ;
        for (int i = 0;i < n;i ++) res.push_back(nums1[i]);
        for (int i = 0;i < m;i++) res.push_back(nums2[i]); 
        sort(res.begin(),res.end());
        if ((n+m)&1) {
            return res[(n+m)/2]*1.0;
        }
        return (res[(n+m)/2] + res[(n+m)/2-1])*1.0/2 ;//记得是double类型
    }
};

思路2--递归

以下代码应用路径在下面链接里面

好的理解路径

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector &nums1, int i, vector &nums2, int j, int k)
    {
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};

后面，我会补上自己的理解。