python写寻找两个正序数组的中位数
时间: 2023-10-23 07:53:52 浏览: 111
寻找两个正序数组的中位数1
题目描述:
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:
输入:nums1 = [,], nums2 = [,]
输出:.00000
示例 4:
输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
nums1.length == m
nums2.length == n
<= m <= 100
<= n <= 100
1 <= m + n <= 200
-106 <= nums1[i], nums2[i] <= 106
解题思路:
首先,我们需要将两个数组合并成一个有序数组,然后再根据数组长度的奇偶性来计算中位数。
对于合并两个有序数组,我们可以使用双指针的方法,从头开始遍历两个数组,每次将较小的数放入新的数组中,直到其中一个数组遍历完毕,然后将另一个数组中剩余的数全部放入新的数组中。
对于计算中位数,我们需要分为两种情况:
当数组长度为奇数时,中位数为新数组的中间数。
当数组长度为偶数时,中位数为新数组的中间两个数的平均数。
代码实现:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 合并两个有序数组
nums = []
i, j = ,
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
nums.append(nums1[i])
i += 1
else:
nums.append(nums2[j])
j += 1
if i < len(nums1):
nums += nums1[i:]
if j < len(nums2):
nums += nums2[j:]
# 计算中位数
n = len(nums)
if n % 2 == :
return (nums[n//2-1] + nums[n//2]) / 2
else:
return nums[n//2]
阅读全文