给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n))
时间: 2024-04-08 13:34:25 浏览: 66
要找出两个正序数组的中位数,可以使用分查找的方法来实现时间复杂度为 O(logm+n))。以下是一个现示例:
```python
def findMedianSortedArrays(nums1, nums2):
m, n = len(nums1), len(nums2)
if m > n:
nums1, nums2, m, n = nums2, nums1, n, m
i_min, i_max, half_len = 0, m, (m + n + 1) // 2
while i_min <= i_max:
i = (i_min + i_max) // 2
j = half_len - i
if i < m and nums2[j-1] > nums1[i]:
# i 太小,增大它
i_min = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
# i 太大,减小它
i_max = i - 1
else:
# i 正好
if i == 0: max_of_left = nums2[j-1]
elif j == 0: max_of_left = nums1[i-1]
else: max_of_left = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = nums2[j]
elif j == n: min_of_right = nums1[i]
else: min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2.0
```
以上代码首先确保 nums1 的长度小于等于 nums2 的长度,然后使用二分查找的方法找到合适的切分点 i,使得左边部分的元素都小于右边部分的元素。最后根据数组的长度是奇数还是偶数,计算中位数并返回。
希望对你有所帮助!
阅读全文