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

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

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

解析

不知道为啥这题标记为困难，两个已经排序了的数组，求中位数，只需要每个数组出一个元素对比，小的数据就寻求下一个数据，继续对比即可，然后累计到中间元素位置，求平均值。

求一个数组的中位数，如果数组长度为奇数，即中间一位元素，如果长度为偶数，即中间两个元素的平均值。

所以我们分别找第 Math.floor((m+n+1)/2) 个，和 Math.floor((m+n+2)/2)个，然后求其平均值即可，这对奇偶数均适用。

var findMedianSortedArrays = function (nums1, nums2) {
  const leftIndex = Math.floor((nums1.length + nums2.length + 1) / 2) - 1; // 左边元素索引
  const rightIndex = Math.floor((nums1.length + nums2.length + 2) / 2) - 1; // 右边元素索引
  let i = 0;
  let j = 0;
  let left; // 左边元素值
  let right; // 右边元素值

  while (i < nums1.length || j < nums2.length) {
    const n1 = nums1[i];
    const n2 = nums2[j];
    // 当 index 超过下标，元素值为 undefined，考虑边界条件
    // 谁小谁先出去
    if (typeof n1 === "undefined" || n1 >= n2) {
      if (i + j === leftIndex) {
        left = n2;
      }
      if (i + j === rightIndex) {
        right = n2;
        // 右边元素找到就退出，不需要继续比较
        break;
      }
      j++;
      continue; // 减少下面的条件判断
    }

    if (typeof n2 === "undefined" || n2 > n1) {
      if (i + j === leftIndex) {
        left = n1;
      }
      if (i + j === rightIndex) {
        right = n1;
        break;
      }
      i++;
    }
  }
  return (left + right) / 2;
};