题目
思路
-
合并，取中位数
归并排序思想合并至中位数位置 -
切分法
转变为在两个有序数组中寻找第k小的数
L奇数时，令k=L/2,结果为f(k+1)
L偶数时，结果为(f(k) + f(k+1))/2
L=len(nums1) + len(nums2)
取nums1的前k1，nums2的前k2个，k1+k2=k，判断最后一位的大小，如果相等，则就是中位数
如果不相等，虽然无法肯定这两个是否是中位数，则可以把问题规模缩小
nums1 = [a0,a1,a2,a3,a4]
nums2 = [b0, b1, b2, b3]
取k=5,k1=3,k2=2
举例
a2<b1
nums1 = [1,2,3,5,6], nums2=[4,7,8,9]
即取[1,2,3]和[4,7]，可以将[1,2,3]排除，因为k1<k，不会在这k1个中 （排除前半部分）
将[8,9]排除，因为3<7，即目前取的k个中7是最大值，所以第k大不会超过7 （排除后半部分）
a2>b1
nums1 = [5,6,7,8,9], nums2=[1,2,3,4]
即取[5,6,7]和[1,2]，可以将[1,2]排除，因为k2<k，不会在这k1个中 （排除前半部分）
将[8,9]排除，因为2<7，即目前取的k个中7是最大值，所以第k大不会超过7 （排除后半部分）
即nums1和nums2的最后一个元素小的必定被排除，最后一个元素大的后面的元素必定被排除
合并法复杂度
-
时间复杂度
两个数组从前到后只遍历一次，O
(
n
)
\mathcal{O}(n)
O(n)
-
空间复杂度
两个数组从前到后只遍历一次，O
(
n
)
\mathcal{O}(n)
O(n)
切分法复杂度
-
时间复杂度
求中位数，k
=
(
m
+
n
)
2
,
k
1
=
k
2
,
k
2
=
k
2
k=\frac{(m+n)}{2}, k_1=\frac{k}{2}, k_2=\frac{k}{2}
k=2(m+n),k1=2k,k2=2k，每次规模减半
类似二分搜索，为O
(
l
o
g
(
(
m
+
n
)
2
)
)
O(log(\frac{(m+n)}{2}))
O(log(2(m+n)))
-
空间复杂度
递归时传递的nums数组不会复制，只使用了常数个变量，O
(
1
)
\mathcal{O}(1)
O(1)
合并，取中位数代码
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
total_length = len(nums1) + len(nums2)
is_odd = total_length % 2
split_location = int(total_length / 2) + 1
i = j = 0
merged_array = list()
while len(merged_array) < split_location: # 个数不够继续循环
if i < len(nums1): # nums1没有取完
if j < len(nums2): # nums1没有取完的情况下，nums2也没有取完，判断应该从哪个列表取
if nums1[i] <= nums2[j]:
merged_array.append(nums1[i])
i += 1
else:
merged_array.append(nums2[j])
j += 1
else: # nums1没有取完，nums2取完了，只在nums1中取
merged_array.append(nums1[i])
i += 1
else: # nums1取完了，则在nums2中取
if j < len(nums2):
merged_array.append(nums2[j])
j += 1
else:
break
# 中位数计算
return merged_array[-1] if is_odd else (merged_array[-1] + merged_array[-2]) / 2
切分法代码
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
k = int((m + n) / 2)
if (m + n) % 2 == 1: # 总长度为奇数，返回第k大的值
return self.find_k_th(nums1, 0, m - 1, nums2, 0, n - 1, k + 1)
else: # 总长度为偶数，返回第k大和第k+1大两个数的平均值
return (self.find_k_th(nums1, 0, m - 1, nums2, 0, n - 1, k)
+ self.find_k_th(nums1, 0, m - 1, nums2, 0, n - 1, k + 1)) / 2.0
def find_k_th(self, nums1, l1, h1, nums2, l2, h2, k):
# 寻找第k小的元素
# 取nums1的[l1, h1]区间和nums2的[l2,h2]区间进行判断
m = h1 - l1 + 1
n = h2 - l2 + 1
if m > n: # m>n，将nums1和nums2互换，加快程序运行
return self.find_k_th(nums2, l2, h2, nums1, l1, h1, k)
if m == 0: # nums1长度为0，返回nums2第k小的数
return nums2[l2 + k - 1]
if k == 1: # k=1时，取最小值，即两个数组最左侧值
return min(nums1[l1], nums2[l2])
# 分别选两个数组的中间数
na = min(int(k / 2), m)
nb = k - na
va = nums1[l1 + na - 1]
vb = nums2[l2 + nb - 1]
if va == vb: # 相等就是中位数
return va
elif va < vb: # 不相等，剪枝，nums1的前na个数和nums2 nb后的数全部排除
return self.find_k_th(nums1, l1 + na, h1, nums2, l2, l2 + nb - 1, k - na)
else: # 不相等，剪枝，nums1 na后的数和nums2 前nb个数全部排除
return self.find_k_th(nums1, l1, l1 + na - 1, nums2, l2 + nb, h2, k - nb)