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;    }  }}

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