题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

中位数

对于一组有限个数的数据来说，其中位数是这样的一种数：这群数据的一半的数据比它大，而另外一半数据比它小。
计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。

解法

解法一

原理： 将两数组将加，然后进行排序，取中位数。
在不考虑时间复杂度的情况下的解法：

var findMedianSortedArrays = function(nums1, nums2) {
    const arr = nums1.concat(nums2);
    arr.sort((a, b) => a-b);

    const len = arr.length;
    if (len%2 === 1) {
      const result = arr[Math.floor(len/2)];

      return result.toFixed(2);
    }

    if (len%2 === 0) {
      const result = (arr[Math.floor(len/2)] + arr[Math.floor(len/2 -1)])/2;
      return result.toFixed(2);
    }
};

解法二

假设有两个有序数组A（m个元素）、B（n个元素）。

中位数切分

var findMedianSortedArrays = function(A, B) {
  let m = A.length;
  let n = B.length;

  // 为了保证 m <= n
  if (m > n) {
    const temp = A;
      A = B;
      B = temp;
    const temp_len = m;
      m = n;
      n = temp_len;
  }

  let i_min = 0, i_max = m, half_len = (m + n + 1) / 2;

  while (i_min <= i_max) {
    const i = Math.floor((i_min + i_max) / 2);
    const j = Math.floor(half_len - i);

    // B[j - 1] > A[j], i 太小需要调大
    if (i < i_max && B[j - 1] > A[i]) {
      i_min = i + 1;
    } else if (i > i_min && A[i-1] > B[j]) {
      i_max = i - 1;
    } else {
      // 获取左边最大值
      let max_left = 0;
      // 当 i=0时，表示集合A左边无数据，则左边最大为 B[j-1]
      if (i == 0) {
        max_left = B[j - 1];
      } else if (j == 0) {
        max_left = A[i - 1];
      } else {
        max_left = Math.max(A[i - 1], B[j - 1]);
      }

      // 若 m + n 为奇数
      if ((m + n) % 2 == 1) {
        return max_left;
      }

      let min_right = 0;
      if (i == m) {
        min_right = B[j];
      } else if (j == n) {
        min_right = A[i];
      } else {
        min_right = Math.min(B[j], A[i]);
      }

      return ((max_left + min_right) / 2).toFixed(2);
    }

  }
  return 0.0;
};

参考资料

• 中位數