题目

题目来源：力扣（LeetCode）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 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

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

思路分析

  1. var findMedianSortedArrays = function (nums1, nums2) {
  2.     // nums1长度比nums2小
  3.     if (nums1.length > nums2.length) {
  4.         [nums1, nums2] = [nums2, nums1];
  5.     }
  6.     let m = nums1.length;
  7.     let n = nums2.length;
  8.     // 在0～m中查找
  9.     let left = 0;
  10.     let right = m;
  11.     // median1：前一部分的最大值
  12.     // median2：后一部分的最小值
  13.     let median1 = 0;
  14.     let median2 = 0;
  15.     while (left <= right) {
  16.         // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
  17.         // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
  18.         const i = left + Math.floor((right - left) / 2);
  19.         const j = Math.floor((m + n + 1) / 2) - i;
  20.         const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
  21.         const minRight1 = i === m ? Infinity : nums1[i];
  22.         const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
  23.         const minRight2 = j === n ? Infinity : nums2[j];
  24.         if (maxLeft1 <= minRight2) {
  25.             median1 = Math.max(maxLeft1, maxLeft2);
  26.             median2 = Math.min(minRight1, minRight2);
  27.             left = i + 1;
  28.         } else {
  29.             right = i - 1;
  30.         }
  31.     }
  32.     return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1;
  33. };

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/