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

题目描述 (opens new window)

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

算法思路

这个解法的思路是利用归并排序的思想，将两个正序数组合并成一个有序数组，然后找到中位数，具体步骤如下。

• 1、计算两个数的长度和，以及中位数的下标 k.
• 2、用两个指针 i 和 j 分别指向两个数组的开头。
• 3、依次比较两个指针所指的元素，将较小的元素加入到合并后的数组中，并将指针移动到下一位。
• 4、如果已经找到了中位数，就返回中位数，如果还没有找到，就继续比较，直到找到中位数为止。

这个解法的时间复杂度是 O(m+n) 其中m和n分别是两个数组的长度，空间复杂度是O(1), 因为只需要用常数个变量来保存中间结果。

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  // 首先计算两个数组的长度
  const m = nums1.length;
  const n = nums2.length;
  // 计算长度的加和
  const total = m + n;
  // 判断加和是不是偶数
  const isEven = total % 2 === 0;
  // 找到中间位置的索引下标
  const k = Math.floor(total / 2);

  // i 和 j 分别指向的是两个数组的开头
  let i = 0;
  let j = 0;
  // 合并后的数组的前一个元素 和当前元素
  let prev = 0;
  let curr = 0;

  for (let l = 0; l <= k; l++) {
    // 将当前元素赋值给前一个元素，以便在下一次的迭代中使用
    prev = curr;
    // 下面这个条件的核心是找出当前循环中较小的一个赋值给curr
    if (i < m && (j >= n || nums1[i] < nums2[j])) {
      curr = nums1[i];
      i++;
    } else {
      curr = nums2[j];
      j++;
    }
  }

  return isEven ? (prev + curr) / 2 : curr;
}

在代码中，我们首先计算了两个数组的长度和中位数的下标，设置了一个变量 isEven 判断总的长度是否为偶数，然后用两个指针 i 和 j分别指向两个数组的开头，用一个循环依次比较两个指针的位置，将较小的元素加入到合并后的数组，并将指针向后移动一位，在循环中我们用变量 prev 和 curr分别保存上一个元素和当前的元素，以便在找到中位数的时候计算中位数的值。最后根据isEven的值返回中位数。

这里面最核心的逻辑就是通过for循环来将两个排序的数组合并成一个有序数组，并且找到合并后数组的中位数，而中位数的位置是由k决定的。在这段代码中，k表示中位数的索引位置，而不是循环的终止条件。

如果数组 nums1 中还有剩余元素 i < m 并且满足以下两个条件之一：

• 数组 nums2 中的元素已经全部加载完毕 j >= n
• 数组 nums1 中当前元素 nums1[i] 小于数组 nums2 中当前元素 nums2[j]

那么就将nums1中当前元素nums1[i]添加到合并后的数组中，并将i增加1，否则表示数组nums2还有剩余元素或者nums1的当前元素大于等于nums2的当前元素nums2[j]添加到合并后的数组中，并将j增加1。

通过以上的逻辑，循环结束之后，合并后的数组中就包含了两个原始数组的所有元素，并且是有序的。

最后，根据中位数的定义，如果数组的总长度是偶数，则将合并后数组中两个相邻元素的平均值作为中位数返回；如果长度是奇数，则直接返回合并后数组的中间元素作为中位数。