返回题库

两个有序数组的中位数

Median of Two Sorted Arrays

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题：两个有序数组的中位数

考察：数组、二分查找

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/median-of-two-sorted-arrays/

英文原题

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
解析

思路：在较短数组上二分切分位置，使左右两边元素数量相等且左半最大值不大于右半最小值。找到合法切分后按总长度奇偶返回中位数。

复杂度：时间 O(log min(m,n))，空间 O(1)。

英文解析

Approach: Binary-search a partition in the smaller array so that the left partitions contain half the elements and every left value is no greater than every right value. The median is determined by the boundary values.

Complexity: Time O(log⁡min⁡(m,n))O(\log \min(m,n)), space O(1)O(1).