Skip to content

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

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

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

要求：时间复杂度为 O(log (m+n))

解法一： 暴力法

  • 归并排序，合并为 m + n 的有序数组
  • 选取合并后数组的中位数
  • 时间复杂度 O(m+n) > O(log (m+n))
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let arr = merge(nums1, nums2);
  let len = arr.length;
  let mid = Math.floor(len / 2);

  if (len % 2) {
    return arr[mid];
  } else {
    return (arr[mid - 1] + arr[mid]) / 2;
  }
};

function merge(nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;

  let _arr = [];
  let i = 0, j = 0, k = 0; // 分别 nums1，nums2，_arr 的指针

  while(k < m + n) {
    if (i >= m) { // nums1 已经遍历完
      _arr[k++] = nums2[j++];
    } else if (j >= n) { // nums2 已经遍历完
      _arr[k++] = nums1[i++];
    } else if (nums1[i] <= nums2[j]) {
      _arr[k++] = nums1[i++];
    } else {
      _arr[k++] = nums2[j++];
    }
  }

  return _arr;
}

解法二： 切分法

  • 转化为在两个有序数组中找第 k 小的数
  • 每次查找规模减半，时间复杂度 O(log (m+n))
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let m = nums1.length;
  let n = nums2.length;
  let k = Math.ceil((m + n) / 2);

  if ((m + n) % 2) {
    return findKth(nums1, 0, m - 1, nums2, 0, n - 1, k);
  } else {
    let x = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k);
    let y = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k + 1);
    return (x + y) / 2;
  }
};

/**
 * 在 nums1 和 nums2 中找到第 k 小的数
 * l1, h1 为 nums1 的搜索范围
 * l2, h2 为 nums2 的搜索范围
 * @return 那个数
 */
function findKth(nums1, l1, h1, nums2, l2, h2, k) {
  let m = h1 - l1 + 1;
  let n = h2 - l2 + 1;

  // 时钟保持 nums1 比 nums2 短，方便计算
  if (m > n) {
    return findKth(nums2, l2, h2, nums1, l1, h1, k)
  }
  // 若 nums1 长度为 0， 则在 nums2 里找
  if (m === 0) {
    return nums2[l2 + k - 1];
  }

  if (k === 1) {
    return Math.min(nums1[l1], nums2[l2]);
  }

  let k1 = Math.floor(k / 2);
  k1 = Math.min(k1, m); // 确保取值不越界
  let k2 = k - k1;
  let value1 = nums1[l1 + k1 - 1];
  let value2 = nums2[l2 + k2 - 1];

  if (value1 === value2) {
    // 1. 找到了这个值, 返回
    return value1;
  } else if (value1 < value2) {
    // 2. 在 nums1 右半侧及 nums2 左半侧继续搜索
    return findKth(nums1, l1 + k1, h1, nums2, l2, l2 + k2 - 1, k - k1);
  } else {
    // 3. 在 nums1 左半侧 nums2 右半侧继续搜索
    return findKth(nums1, l1, l1 + k1 - 1, nums2, l2 + k2, h2, k - k2);
  }
}

拓展一： 数组未排序

思考：给定两个数组未排序，如何取出中位数？

  • 快速选择算法：在 O(n) 时间内选出未排序数组中第 k 小的数。
  • 最终，时间复杂度 O(m + n)，空间复杂度 O(1)

215. 数组中的第K个最大元素

  • 快速选择算法
  • 时间复杂度分析 O(n)
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  return quickSelect(nums, 0, nums.length - 1, k);
};

function quickSelect(nums, lo, hi, k) {
  // 1. 分区 O(n)
  let pivot = partion(nums, lo, hi);

  let count =  pivot - lo + 1; // 左侧计数

  // 2. 递归 T(n / 2)
  if (k === count) {
    return nums[pivot];
  } else if (k < count) {
    // 往左侧搜索
    return quickSelect(nums, lo, pivot - 1, k);
  } else {
    // 往右侧搜索
    return quickSelect(nums, pivot + 1, hi, k - count);
  }
}

// 分区：左侧大右侧小
function partion(nums, lo, hi) {
  let pivot = lo;
  let pivotVal = nums[pivot];

  for (let i = lo; i <= hi; i++) {
    if (nums[i] > pivotVal) {
      nums[pivot++] = nums[i];
      nums[i] = nums[pivot];
    }
  }
  nums[pivot] = pivotVal;

  return pivot;
}

时间复杂度分析

  • 第一次运行 T(n) = T(n / 2) + n,
  • 第二次运行 T(n / 2) = T(n / 4) + n / 2,
  • ...
  • T(2) = T(1) + 2;
  • 计算得出，T(n) = n + n / 2 + n / 4 + ... + 2 + T(1) = 2 * n;
  • 因此，O(T(n)) = O(n).

拓展二：分布式海量数据

思考：一万个服务器，每个服务器存储十亿个未排序的数，如何找到中位数？

  • 考虑空间复杂度：快排对内存开销比较小
  • 考虑整体时间复杂度：
    • Mater 与各个节点通信 O(logn) 次，每次通信内容为一个基准值和三个计数值
    • 整体时间复杂度：O(nlogn)

算法思想：

  1. 从一万个服务器中随机选择一台为 Mater，主导快速选择算法；
  2. Mater 上随机选择基准值，然后广播到其他服务器；
  3. 每台服务器开始执行快速选择算法，小于基准值的放数组左边，大于的放右边；同时，记住每台最后小于 、等于、大于基准值的数量：less count, equal count, greater count;
  4. 将所有 count 发送回 Mater；
  5. Mater 计算所有 less count, equal count, greater count 总和，并确定下一次选择范围。