给定两个大小分别为 m和口的正序(从小到大)教组nums1 和nums2。请你找出并返回这两个正序 数組的 中位数。
时间: 2024-05-01 12:23:51 浏览: 166
寻找两个正序数组的中位数1
这道题可以使用归并排序的思想来解决。
首先将两个数组合并成一个有序数组,然后根据数组长度的奇偶性来确定中位数的位置。
如果数组长度为奇数,则中位数为排序后的数组的中间位置对应的元素。
如果数组长度为偶数,则中位数为排序后的数组的中间两个元素的平均值。
下面是代码实现:
```python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m > n:
nums1, nums2, m, n = nums2, nums1, n, m
imin, imax = 0, m
while imin <= imax:
i = (imin + imax) // 2
j = (m + n + 1) // 2 - i
if i < m and nums2[j-1] > nums1[i]:
imin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
imax = i - 1
else:
if i == 0:
max_left = nums2[j-1]
elif j == 0:
max_left = nums1[i-1]
else:
max_left = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return max_left
if i == m:
min_right = nums2[j]
elif j == n:
min_right = nums1[i]
else:
min_right = min(nums1[i], nums2[j])
return (max_left + min_right) / 2
```
阅读全文