题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
1
2
3
| 输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
|
示例 2：
1
2
3
| 输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
|
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
简介
1
2
3
4
5
6
7
8
9
10
11
12
| 讨论在两个有序数组中寻找中位数的问题
观察单个有序数组，通过比较元素大小找到舍弃的元素，确定中位数。
类推两个有序数组，准备两个区间来存放偏小值和偏大值。
根据区间需要满足必要条件，使得偏小区间的元素都小于偏大区间。
问题转化为在单个有序数组中查找满足条件的关键元素位置，可以使用二分查找。
关键词:
偏小区间
偏大区间
二分查找
|
正文
首先思考我们是否可以避免全排序找到中位数
我们有一种想法就是通过比较元素的大小找到需要舍弃的元素
我们观察一个有序数组，我们准备两个区间 RSmall, RBig 分别存放这个数组的偏小值与偏大值（相对中位数而言）
分别用 left，right 指针从两头操作偏小值与偏大值，将他们依次放入对应的数组
直到 「偶数时 RSmall.size = RBig.size 或者 奇数时 RSmall.size = RBig.size + 1」，中位数显然易得
好，现在我们来看两个有序数组的复杂情况
我们同样准备两个区间 RSmall, RBig，同样我们需要将数组偏小值放进 RSmall，偏大值放进 RBig
与一个有序数组不同的是，现在我们必须综合考虑两个有序数组的情况
所以 RSmall 区间里可能既包含 num1 数组的偏小元素也包含 num2 数组的偏小元素，对于RBig也是一样
这就让我们的思考变得复杂了，这使得 RSmall，RBig 变得无序
现在将这个 RSmall 再细分为 RSmallN1 区间，以及 RSmallN2 区间，同样有 RBigN1，RBigN2 区间
想要得到中位数，那么偶数时 RSmall.size = RBig.size 或者 奇数时 RSmall.size = RBig.size + 1
也就有
「 必要条件一： 偶数时 RSmallN1.size + RSmallN2.size = RBigN1.size + RBigN2.size 奇数时 RSmallN1.size + RSmallN2.size = RBigN1.size + RBigN2.size +1 」
同时 RSmall 区间内任何一个元素都必须小于 RBig 区间
自然有 Small 区间的子区间的任何一个元素都小于 Big 区间的子区间的任何一个元素
所以得到
「 必要条件二： RSmallN1 的最大值 < RBigN1 的最小值 ( 因为数组有序，这是不用判断的 ) RSmallN1 的最大值 < RBigN2 的最小值 RSmallN2 的最大值 < RBigN1 的最小值 RSmallN2 的最大值 < RBigN2 的最小值 ( 因为数组有序，这是不用判断的 )」
简化一下
「 必要条件二： maxOf( RSmallN1 ) < minOf ( RBigN2 ) maxOf( RSmallN2 ) < minOf ( RBigN1 ) 」
显然必要条件一加上必要条件二就是充分必要条件
现在我们要得到这四个区间，或者说要在两个有序数组分别划分出这四个区间
我们要在这两个数组中分别找到关键的那个分隔元素
因为必要条件一的原因，我们找到了 num1 数组的分割元素，我们也就找到了 num2 数组的分割元素
这非常好理解，因为 Small 区间和 Big 区间的数量是固定的，RSmallN1 多了一个元素，RSmallN2 就要对应减少一个元素
所以我们只要找到 num1 数组的分隔元素即可
至此，问题成功转化成了
在 num1 数组中查找出一个关键元素位置，这个关键元素满足上述两条必要条件
这是一个典型的有判断条件的查找问题，我们就可以使用二分查找，测试每个元素是否符合上述两个条件
关于二分查找这里不再赘述。
以下是基于二分查找的 Kotlin 代码实现，用于找出两个有序数组的中位数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val n1 = nums1.size
val n2 = nums2.size
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1)
}
var left = 0
var right = n1
while (left <= right) {
val num1HalfIndex = (left + right) / 2
val num2HalfIndex = ((n1 + n2 + 1) / 2) - num1HalfIndex
val maxOfNum1SmallRange = if (num1HalfIndex == 0) Int.MIN_VALUE else nums1[num1HalfIndex - 1]
val minOfNum1BigRange = if (num1HalfIndex == n1) Int.MAX_VALUE else nums1[num1HalfIndex]
val maxOfNum2SmallRange = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
val minOfNum2BigRange = if (j == n2) Int.MAX_VALUE else nums2[j]
if (maxOfNum1SmallRange <= minOfNum2BigRange && maxOfNum2SmallRange <= minOfNumBigRange) {
return if ((n1 + n2) % 2 == 0) {
(maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble() + minOf(minOfNum1BigRange, minOfNum2BigRange).toDouble()) / 2.0
} else {
maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble()
}
} else if (maxOfNum1SmallRange > minOfNum2BigRange) {
right = num1HalfIndex - 1
} else {
left = num1HalfIndex + 1
}
}
return 0.0
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val n1 = nums1.size
val n2 = nums2.size
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1)
}
var left = 0
var right = n1
while (left <= right) {
val num1HalfIndex = (left + right) / 2
val num2HalfIndex = ((n1 + n2 + 1) / 2) - num1HalfIndex
val maxOfNum1SmallRange = if (num1HalfIndex == 0) Int.MIN_VALUE else nums1[num1HalfIndex - 1]
val minOfNum1BigRange = if (num1HalfIndex == n1) Int.MAX_VALUE else nums1[num1HalfIndex]
val maxOfNum2SmallRange = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
val minOfNum2BigRange = if (j == n2) Int.MAX_VALUE else nums2[j]
if (maxOfNum1SmallRange <= minOfNum2BigRange && maxOfNum2SmallRange <= minOfNumBigRange) {
return if ((n1 + n2) % 2 == 0) {
(maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble() + minOf(minOfNum1BigRange, minOfNum2BigRange).toDouble()) / 2.0
} else {
maxOf(maxOfNum1SmallRange, maxOfNum2SmallRange).toDouble()
}
} else if (maxOfNum1SmallRange > minOfNum2BigRange) {
right = num1HalfIndex - 1
} else {
left = num1HalfIndex + 1
}
}
return 0.0
}
|
留给大家一个问题，问 N 个有序数组的中位数怎么求？
