Description:
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)).
You may assume nums1 and nums2 cannot be both empty.
- Example 1:
- nums1 = [1, 3]
- nums2 = [2]
- The median is 2.0
- Example 2:
- nums1 = [1, 2]
- nums2 = [3, 4]
- The median is (2 + 3)/2 = 2.5
描述:
两个有序数组 nums1 和 nums2, 数组元素数量分别为 m 和 n.
寻找两个数组的中位数. 要求程序的时间复杂度为 O(lg(m+n)).
假设数组 nums1 和 nums2 不同时为空.
示例 1:
- nums1 = [1, 3]
- nums2 = [2]
中位数为 2.0
示例 2:
- nums1 = [1, 2]
- nums2 = [3, 4]
中位数为 (2 + 3) / 2 = 2.5
方法:
首先, 我们先理解中位数的概念和意义. 中位数, 又称中点数, 中值. 中数是按顺序排列的一组数据中居于中间位置的数, 即在这组数据中, 有一半的数据比他大, 有一半的数据比他小. 对于有限的数集, 可以通过把所有观察值高低排序后找出正中间的一个作为中位数. 如果观察值有偶数个, 通常取最中间的两个数值的平均数作为中位数.
来源: http://www.bubuko.com/infodetail-2727592.html