1. 题目描述

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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

  1. 输入：nums1 = [1,3], nums2 = [2]
  2. 输出：2.00000
  3. 解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

  1. 输入：nums1 = [1,2], nums2 = [3,4]
  2. 输出：2.50000
  3. 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

  1. 输入：nums1 = [0,0], nums2 = [0,0]
  2. 输出：0.00000

示例 4：

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

示例 5：

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

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000

  • -106 <= nums1[i], nums2[i] <= 106

    2. 解题思路

    首先能想到的就是合两个数组，找出中位数，其大致思路如下：

  • 设置两个指针，分别指向两个数组

  • 每次将两个指针指向的元素进行对比，将减小的元素放入合并后的数组中，这样就实现了两个数组的有序合并
  • 最后，判断合并后的数组长度的奇偶性，求出数组的中位数。


复杂度分析：**

  • 时间复杂度：O(m+n)，其中m和n是两个数组的长度；

  • 空间复杂度：O(m+n)，我们需要一个长度m+n的数组来储存两个数组元素合并后的元素。

    2. 代码实现**

    1. /**
    2. * @param {number[]} nums1
    3. * @param {number[]} nums2
    4. * @return {number}
    5. */
    6. var findMedianSortedArrays = function(nums1, nums2) {
    7.   const len1 = nums1.length
    8.   const len2 = nums2.length
    9.   const merge = new Array(len1 + len2)
    10.   let i = 0, j = 0, k = 0;
    11.   while (i < len1 && j < len2) {
    12.       merge[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
    13.   }
    14.   while (i < len1) {
    15.       merge[k++] = nums1[i++];
    16.   }
    17.   while (j < len2) {
    18.       merge[k++] = nums2[j++];
    19.   }
    21.   const len = merge.length
    22.   return len % 2 == 0 ? (merge[len / 2] + merge[len / 2 - 1]) / 2 : merge[(len - 1) / 2];
    23. };

    4. 提交结果**

    4. 寻找两个正序数组的中位数 - 图1