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

链接：4.寻找两个正序数组的中位数
难度：Hard
标签：数组、二分查找、分治
简介：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

题解 1 - typescript

• 编辑时间：2020-05-24
• 执行用时：144ms
• 内存消耗：42.2MB
• 编程语言：typescript
• 解法介绍：合并数组排序后直接求两个中间值。

var findMedianSortedArrays = function (nums1: number[], nums2: number[]): number {
  const len = nums1.length + nums2.length;
  const mid1 = len >> 1;
  const mid2 = len % 2 === 0 ? mid1 - 1 : mid1;
  const arr = [...nums1, ...nums2].sort((a, b) => a - b);
  return (arr[mid1] + arr[mid2]) / 2;
};

题解 2 - typescript

• 编辑时间：2021-07-23
• 执行用时：124ms
• 内存消耗：42.9MB
• 编程语言：typescript
• 解法介绍：二分查找。

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  const n1 = nums1.length;
  const n2 = nums2.length;
  const v1 = find((n1 + n2 + 1) >> 1);
  if ((n1 + n2) % 2 === 1) return v1;
  const v2 = find(((n1 + n2 + 1) >> 1) + 1);
  return (v1 + v2) / 2;
  function find(k: number, i1: number = 0, i2: number = 0): number {
    if (i1 === nums1.length) return nums2[i2 + k - 1];
    if (i2 === nums2.length) return nums1[i1 + k - 1];
    if (k === 1) return Math.min(nums1[i1], nums2[i2]);
    let v1 = Math.min(k >> 1, nums1.length - i1);
    let v2 = Math.min(k - v1, nums2.length - i2);
    v1 = k - v2;
    if (nums1[i1 + v1 - 1] <= nums2[i2 + v2 - 1]) return find(k - v1, i1 + v1, i2);
    else return find(k - v2, i1, i2 + v2);
  }
}