BFE.devAI解答 - JavaScript 代码题
136. 两个已排序数组的中位数

解法一：归并排序

由于两个数组已经有序，可以利用归并排序的思路进行合并，并找到中位数。

具体来说，可以用两个指针分别指向两个数组的起始位置，每次比较两个指针所在位置的数字大小，较小的那个加入合并后的数组中，并将对应指针向后移动一位。重复这个过程，直到合并后的数组长度达到中位数位置。如果数字总数是奇数，中位数是合并后数组的最后一个数字；如果是偶数，中位数是合并后数组的最后两个数字的平均数。

时间复杂度：O(m+n)，其中 m 和 n 分别为两个数组的长度。

空间复杂度：O(m+n)，需要开辟一个新的数组来存储合并后的数组。

代码如下：

function median(nums1, nums2) {
  const merged = [];
  let i = 0,
    j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) {
      merged.push(nums1[i]);
      i++;
    } else {
      merged.push(nums2[j]);
      j++;
    }
  }
  while (i < nums1.length) {
    merged.push(nums1[i]);
    i++;
  }
  while (j < nums2.length) {
    merged.push(nums2[j]);
    j++;
  }
  const len = merged.length;
  return len % 2 == 0 ? (merged[len / 2 - 1] + merged[len / 2]) / 2 : merged[Math.floor(len / 2)];
}

时间复杂度已经是最优解了，但是空间复杂度较高。考虑优化一下空间复杂度。

解法二：二分查找

如果要求的是中位数，那么可以将两个已排序的数组合并为一个排序数组后，直接找到中位数。但是这种方法需要 O(m+n) 的时间和空间复杂度。

由于两个数组已经有序，可以考虑使用二分查找的方法。假设中位数是 m，那么要找到 m，在两个数组中需要找到两个位置 i 和 j，这两个位置满足：

1. 左数组 nums1 中 [0, i-1] 的数都小于 m；
2. 右数组 nums1 中 [i, m-1] 的数都大于 m；
3. 左数组 nums2 中 [0, j-1] 的数都小于 m；
4. 右数组 nums2 中 [j, n-1] 的数都大于 m；

注意，i 和 j 可以为 0 和 n，这表示前一个数组或后一个数组为空。

根据条件可知，i,j的值范围均在 [0, m] 和 [0, n] 之间。所以可以通过二分查找从 nums1 中找到合适的 i，剩下的 j 可以求得。

假设 nums1 的长度为 m，nums2 的长度为 n。另 k = (m + n) / 2，当 k 为整数时，中位数即为 k 和 k+1 位置的数字的平均值；当 k 为奇数时，中位数即为第 k+1 个数字。

时间复杂度：O(log(min(m,n)))，其中 m 和 n 分别为两个数组的长度。

空间复杂度：O(1)，只需要常数级别的空间。

代码如下：

function median(nums1, nums2) {
  const m = nums1.length,
    n = nums2.length;
  let iMin = 0,
    iMax = m,
    halfLen = Math.floor((m + n + 1) / 2);
  while (iMin <= iMax) {
    let i = Math.floor((iMin + iMax) / 2);
    let j = halfLen - i;
    if (i < iMax && nums2[j - 1] > nums1[i]) {
      iMin = i + 1; // i 太小了，需要增大
    } else if (i > iMin && nums1[i - 1] > nums2[j]) {
      iMax = i - 1; // i 太大了，需要减小
    } else {
      let maxLeft = 0;
      if (i == 0) {
        maxLeft = nums2[j - 1];
      } else if (j == 0) {
        maxLeft = nums1[i - 1];
      } else {
        maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
      }
      if ((m + n) % 2 == 1) {
        return maxLeft;
      }

      let minRight = 0;
      if (i == m) {
        minRight = nums2[j];
      } else if (j == n) {
        minRight = nums1[i];
      } else {
        minRight = Math.min(nums1[i], nums2[j]);
      }

      return (maxLeft + minRight) / 2;
    }
  }
}

综上所述，两种方法的时间复杂度是相同的，但空间复杂度上二分查找更优秀。