4. 寻找两个正序数组的中位数
hard
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。
算法的时间复杂度应该为 $O(log (m+n))$。
Python 的奇技淫巧
有排序，有合并数组，显然没有达到指定的时间复杂度。。。
1
2
3
4
5
6
7
| class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums=sorted(nums1+nums2)
if len(nums)%2==0:
return (nums[len(nums)//2]+nums[len(nums)//2-1])/2.0
else:
return nums[len(nums)//2]
|
二分查找
这道题让我们求两个有序数组的中位数，而且限制了时间复杂度为 O(log (m+n))，看到这个时间复杂度，自然而然的想到了应该使用二分查找法来求解。
那么回顾一下中位数的定义，如果某个有序数组长度是奇数，那么其中位数就是最中间那个，如果是偶数，那么就是最中间两个数字的平均值。
这里对于两个有序数组也是一样的，假设两个有序数组的长度分别为 m 和 n，由于两个数组长度之和 m+n 的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。
为了简化代码，不分情况讨论，我们使用一个小 trick，我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。加入 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以 2，还是其本身。
这里我们需要定义一个函数来在两个有序数组中找到第 K 个元素，下面重点来看如何实现找到第 K 个元素。
首先，为了避免产生新的数组从而增加时间复杂度，我们使用两个变量 i 和 j 分别来标记数组 nums1 和 nums2 的起始位置。然后来处理一些边界问题
- 比如当某一个数组的起始位置大于等于其数组长度时，说明其所有数字均已经被淘汰了，相当于一个空数组了，那么实际上就变成了在另一个数组中找数字，直接就可以找出来了。
- 还有就是如果 K=1 的话，那么我们只要比较 nums1 和 nums2 的起始位置 i 和 j 上的数字就可以了。
难点就在于一般的情况怎么处理？因为我们需要在两个有序数组中找到第 K 个元素，为了加快搜索的速度，我们要使用二分法，对 K 二分，意思是我们需要分别在 nums1 和 nums2 中查找第 K/2 个元素，注意这里由于两个数组的长度不定，所以有可能某个数组没有第 K/2 个数字，所以我们需要先检查一下，数组中到底存不存在第 K/2 个数字，如果存在就取出来，否则就赋值上一个整型最大值。
- 如果某个数组没有第 K/2 个数字，那么我们就淘汰另一个数字的前 K/2 个数字即可。
- 有没有可能两个数组都不存在第 K/2 个数字呢，这道题里是不可能的，因为我们的 K 不是任意给的，而是给的 m+n 的中间值，所以必定至少会有一个数组是存在第 K/2 个数字的。
最后就是二分法的核心啦，比较这两个数组的第 K/2 小的数字 midVal1 和 midVal2 的大小：
- 如果第一个数组的第 K/2 个数字小的话，那么说明我们要找的数字肯定不在 nums1 中的前 K/2 个数字，所以我们可以将其淘汰，将 nums1 的起始位置向后移动 K/2 个，并且此时的 K 也自减去 K/2，调用递归。
- 反之，我们淘汰 nums2 中的前 K/2 个数字，并将 nums2 的起始位置向后移动 K/2 个，并且此时的 K 也自减去 K/2，调用递归即可。
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
| func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
length := len(nums1)+len(nums2)
if length%2 == 1{
return float64(getKthElement(nums1, nums2, length/2+1))
}
k1, k2 := length/2, length/2+1
return float64(getKthElement(nums1,nums2,k1)+getKthElement(nums1,nums2,k2))/2.0
}
// 二分查找 找到第k小的元素
func getKthElement(nums1, nums2 []int, k int)int{
m, n := len(nums1), len(nums2)
index1, index2 := 0, 0
for {
if m == index1{
return nums2[index2+k-1]
}
if n == index2{
return nums1[index1+k-1]
}
if k == 1{
return Min(nums1[index1], nums2[index2])
}
half := k/2
l1 := Min(index1+half, m)-1
l2 := Min(index2+half, n)-1
pivot1, pivot2 := nums1[l1], nums2[l2]
if pivot1 <= pivot2{
k -= l1-index1+1
index1 = l1+1
}else{
k -= l2-index2+1
index2 = l2+1
}
}
}
func Min(a, b int)int{
if a < b{
return a
}
return b
}
|
归并排序
将这两个有序数组合并后找中位数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func FindMedianSortedArrays(nums1, nums2 []int) float64 {
var res []int
m, n := len(nums1), len(nums2)
l1, l2 := 0, 0
for l1 < m && l2 < n{
if nums1[l1] < nums2[l2]{
res = append(res, nums1[l1])
l1++
}else{
res = append(res, nums2[l2])
l2++
}
}
res = append(res, nums1[l1:]...)
res = append(res, nums2[l2:]...)
length := m + n
if length % 2 == 1{
return float64(res[length/2])
}
mid1 := res[length/2]
mid2 := res[length/2-1]
return float64(mid1 + mid2)/2.0
}
|
双指针
本质上还是归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
length := m + n
left, right := 0, 0
l1, l2 := 0, 0
// 如果length为奇数，那问题转换为求第k小的数(k=length/2+1)
// 所以循环k-1次，迭代right即可得到第k小的数
// 如果length为偶数，那么问题转换为求第k-1小的数和第k小的数两个数的平均值
for i := 0; i <= length/2; i++ {
left = right
if l1 < m && (l2 >= n || nums1[l1] < nums2[l2]) {
right = nums1[l1]
l1++
} else {
right = nums2[l2]
l2++
}
}
if length%2 == 1 {
return float64(right)
}
return float64(left+right) / 2.0
}
|
