给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。帮我写一段c++代码

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (m+n))。

示例

示例 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 == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106

算法1

(二分查找) $O(log(min(m,n)))$

时间复杂度

参考文献

python3 代码

C++ 代码

java 代码

算法2

(暴力枚举) $O(m+n)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数

### 回答1：
中位数是指将一个集合分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。对于给定的两个正序数组，可以将它们合并成一个有序数组，然后找到这个有序数组的中位数。

如果两个数组的长度之和为奇数，中位数就是有序数组中间的那个元素；如果长度之和为偶数，中位数就是有序数组中间两个元素的平均值。

具体实现可以使用归并排序的思想，将两个数组合并成一个有序数组，然后根据长度之和的奇偶性找到中位数。时间复杂度为 O(m+n)。

### 回答2：
题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，请你找出并返回这两个正序数组的中位数。

示例

示例1：

输入：
nums1 = [1,3]
nums2 = [2]
输出：2

示例2：

输入：
nums1 = [1,2]
nums2 = [3,4]
输出：2.5

解释：
合并数组后为 [1,2,3,4]，中位数为 (2 + 3) / 2 = 2.5

解法

由于已知nums1和nums2都是正序，所以我们可以分别尝试对两个数组进行二分查找，找到两个数组的中位数对应的位置。

首先，选定两个数组中位数的位置：

- 对于一个长度为n的正序数组，中位数的位置可以是n/2，也可以是(n-1)/2，因为n/2就是中位数所在的位置，但(n-1)/2和n/2的结果是一样的，因为这两个位置对应的两个数的差值对中位数的影响是一样的。
- 所以对于长度为m的nums1和长度为n的nums2，选定中位数的位置应该是(m+n+1)/2和(m+n+2)/2两个位置。

然后，我们对nums1进行二分查找，找到一个位置i，使得：

nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]

我们可以将这个位置i称为“分割线”，分割线左边的元素可以组成一个长度为i+j-1的有序数组，右边的元素可以组成一个长度为m+n-i-j+1的有序数组。

对于奇数的情况，中位数就是分割线左边的元素和分割线右边的元素中较大的那个。

对于偶数的情况，中位数就是分割线左边的元素和分割线右边的元素的平均数。

代码

### 回答3：
首先，我们需要了解中位数的定义。中位数是一组数据中居于中间位置的数，即把一组数从小到大或从大到小排序后，位于中间位置（如果有偶数个数，则取中间两个数的平均值）的数字。因此，要求解这两个正序数组的中位数，我们需要先将它们合并成一个有序数组，然后找出中间位置的数或两个数的平均值。

合并两个有序数组的方法有很多种，这里介绍一种比较简单的方法：使用双指针法，分别指向两个数组的起始位置，逐个比较两个指针所指的数，将较小的数存入一个新数组中，并将指针后移，直到任意一个数组的数被取完，再将剩余的数组中的数依次存入新数组中。最终得到的新数组就是合并后的有序数组。

接下来，我们需要确定中位数的位置。假设两个有序数组的长度分别为 m 和 n，那么它们的中位数要么是第 (m+n)/2 个数，要么是第 (m+n)/2 和 (m+n)/2+1 个数的平均值（当 m+n 为偶数时）。

因此，我们可以使用双指针法，同时遍历两个有序数组，记录已经遍历的数的个数，当遍历到第 (m+n)/2 或 (m+n)/2+1 个数时，就可以得到中位数。

下面是使用双指针法求解两个有序数组的中位数的 Python 代码实现：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        nums = []
        i, j = 0, 0
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums.append(nums1[i])
                i += 1
            else:
                nums.append(nums2[j])
                j += 1
        nums += nums1[i:]
        nums += nums2[j:]
        k = (m + n) // 2
        if (m + n) % 2 == 0:
            return (nums[k-1] + nums[k]) / 2
        else:
            return nums[k]

该算法的时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。需要注意的是，由于 Python 中整数除法运算会向下取整，因此计算中位数位置时需要使用 (m+n)//2 和 (m+n)//2+1。

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你用python编程语言找出并返回这两个正序数组的 中位数 。

在给定的两个数组 nums1 和 nums2 中找到中位数，可以使用归并排序的思想。首先合并两个数组，再找出合并后数组的中位数。

如果合并后的数组的长度是奇数，那么中位数即为该数组的第 (m+n+1)//2 个数字。

如果合并后的数组的长度是偶数，那么中位数即为该数组第 (m+n)//2 和 (m+n)//2+1 个数字的平均数。

下面是代码示例：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if i < m and nums2[j-1] > nums1[i]:
                imin = i + 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                imax = i - 1
            else:
                if i == 0: max_of_left = nums2[j-1]
                elif j == 0: max_of_left = nums1[i-1]
                else: max_of_left = max(nums1[i-1], nums2[j-1])
                if (m + n) % 2 == 1:
                    return max_of_left
                if i == m: min_of_right = nums2[j]
                elif j == n: min_of_right = nums1[i]
                else: min_of_right = min(nums1[i], nums2[j])
                return (max_of_left + min_of_right) / 2.0

这段代码中，使用二分查找的方法来找到合并后数组的中位数。