给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
普通解法
合并两个数组，进行排序，然后判断长度奇数，偶数
1.奇数则取中间那个
2.偶数则取中间两个的和除以2
python
1
2
3
4
5
6
7
8
9
| class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1.sort()
n = len(nums1)
if n%2 != 0:
return nums1[int((n - 1)/2)]
else:
return (nums1[int(n/2) - 1] + nums1[int(n/2)])/2
|
时间复杂度是 O(m+n)，空间复杂度是 O(m+n)
优化：二分查找
不需要合并两个数组，再去找中位数的位置，两个有序数组，可根据下标，直接去找中位数的位置
当 m+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2 个元素，当 m+n 是偶数时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为 (m+n)/2或 (m+n)/2+1。
判断2个有序数组的长度和 m+n
长度和为奇数：k=((m+n) +1)/2,第k个数为中位数
长度和为偶数：k1=(m+n)/2，k2=(m+n)/2 + 1，这两个数的平均值为中位数
都是有序数组，就是找第k小的数，或者找第k，与第k+1小的数
假设A,B两个数组，比较A[k/2-1]和B[k/2-1]
1.如果A[k/2-1]<B[k/2-1],则比A[k/2−1]小的数最多只有A 的前k/2−1 个数和B 的前k/2−1 个数，即比A[k/2−1] 小的数最多只有k−2 个，因此A[k/2−1]不可能是第k个数A[0]到A[k/2−1]也都不可能是第k个数，可以全部排除
PS: 排除A里面的A[0]到A[k/2−1]
2.如果A[k/2−1]>B[k/2−1]，则可以排除B[0]到B[k/2−1]，与上面同理
3.如果A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理
比较完之后，可以发现，排除了k/2 个不可能是第k小的数，查找范围缩小了一半
然后继续二分查找，同时根据排除的个数，减少k的值
特殊处理的情况：
1.如果A[k/2−1]或者B[k/2−1]越界,那么我们可以选取对应数组中的最后一个元素。
在这种情况下，我们必须根据排除数的个数减少k的值，而不能直接将k减去k/2。
2.如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 kk 小的元素。
3.如果k=1，我们只要返回两个数组首元素的最小值即可
python
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
| class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 二分查找，找两个数组里第k小的数
def getKthElement(k):
# 双指针，两个数组。不包含已排除的有效起始索引下标
index1, index2 = 0, 0
while True:
# 特殊情况，while循环的结束条件
if index1 == m:
# 如果1的索引下标到达了数组长度，也就是0，则数组1都被排除了，返回数组2的剩下的中位数
return nums2[index2 + k - 1]
if index2 == n:
# 如果2的索引下标到达了数组长度，也就是0， 则数组2都被排除了，返回数组1的剩下的中位数
return nums1[index1 + k - 1]
if k == 1:
# 如果k为1，则数组长度为1，则返回两个数组的最小值
return min(nums1[index1], nums2[index2])
# 正常情况
# 计算新的k得到的下标，与最大下标的最小值，防止越界
newIndex1 = min(index1 + k
newIndex2 = min(index2 + k
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
# 比较两个值，小于等于，第一种情况
if pivot1 <= pivot2:
# 第一个数组的值小于第二个数组的值，则排除第一个数组的值之前的元素
# 然后偏移k，k减去 新的起始索引减去老的起始索引，即排除的元素
k -= newIndex1 - index1 + 1
# 第一个数组往后挪一位，比较后面的，前面的已经被排除了，得到下一个的起始索引
index1 = newIndex1 + 1
else:
# 第一个数组的值大于第二个数组的值，则排除第二个数组的值之前的元素
# 然后偏移k，k减去 新的起始索引减去老的起始索引，即排除的元素
k -= newIndex2 - index2 + 1
# 第二个数组往后挪一位，比较后面的，前面的已经被排除了，得到下一个的起始索引
index2 = newIndex2 + 1
1.这里开始 # 得到两个数组的长度
m, n = len(nums1), len(nums2)
totalLength = m + n
# 总长度取余，如果有余数是1，就是奇数，+1除以2，得到k，找第k小的数
if totalLength % 2 == 1:
return getKthElement((totalLength + 1)
# 否则就是偶数，除以2得到k，找第k小的数与找第k+1小的数，求和除以2，得到最后的值
else:
return (getKthElement(totalLength
|
时间复杂度：O(log(m+n))，其中 m 和 n 分别是数组nums1和nums2的长度。初始时有 k=(m+n)/2 或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))。
空间复杂度：O(1)