需求
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2厂汗。
請你找出這兩個(gè)有序數(shù)組的中位數(shù)业崖，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))野芒。
你可以假設(shè) nums1 和 nums2 不會同時(shí)為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
解決思路
- 合并2個(gè)列表双炕，并排序(升序)狞悲；
- 如果合并后的列表元素個(gè)數(shù)為奇數(shù)，直接取最中間的元素妇斤；
- 如果合并后的列表元素個(gè)數(shù)為偶數(shù)摇锋，則取最中間的2個(gè)元素的均值。
參考代碼
nums1 = [1, 3]
nums2 = [2, 4]
def get_medians(nums1, nums2):
item = nums1 + nums2
item.sort()
count = len(item)
if count % 2 == 1:
return item[count // 2]
else:
return (item[count // 2] + item[count // 2 - 1]) / 2
print(get_medians(nums1, nums2))
2.5
