Median of Two Sorted Arrays

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 842 | 阅读时长 ≈ 1 分钟

题目出处

源自于leetcode

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0

1
2
3
4
5
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解读

给定两个有序数组，长度分别为m和n，找到两个数组的中位数。时间复杂度应该为O(log(m+n))

初步思路

什么是中位数

当变量值的项数N为奇数时，处于中间位置的变量值即为中位数；当N为偶数时，中位数则为处于中间位置的2个变量值的平均数。
中位数的解释参见百度百科

如何获取中位数

在python，由于语言特性，可以忽略数组总长度（len）为奇数还是偶数，即取(len/2 + (len - 1)/2)/2的值为中位数。举例如下：

  1. 当数组长度为3时,各个数字的下标为[0, 1, 2], 3/2=1， (3-1)/2=1, 计算下标为1的值两次再除以2.0，刚好是自己本身（还可以将整型转化为浮点型）；
  2. 当数组长度为4时,各个数字的下标为[0, 1, 2, 3]，4/2=2， (4-1)/2=1，计算下表为1和2的两个值的和再除以2.0即为中位数。

也就是从两个有序数组中取出从小到大排序后下标分别为(m + n - 1)/2和(m + n)/2的两个值，相加后除以2.0即为答案。

解法

题目要求算法复杂度为O(log(m + n))，直观想到的解法有两种：

  1. 直接在两个数组中采用二分查找法查找两个下标值；
  2. 先排序，然后直接获取。
0%