描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 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 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Related Topics
- 数组
- 二分查找
- 分治
👍 4921
👎 0
题解
python
先来偷个懒，排序用python内置排序
"""
6:52 PM info
解答成功:
执行耗时:32 ms,击败了92.13% 的Python用户
内存消耗:13.1 MB,击败了77.32% 的Python用户
"""
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
nums = nums1 + nums2
nums.sort()
ss = len(nums) // 2
ee = len(nums) % 2
if ee:
return nums[ss]
# {:.5f}.format(restule)
# Decimal(restule).quantize(Decimal("0.00"))
# 这里题目虽然后面跟小数点了但是实际返回不要求，但是必须是浮点型
return float((nums[ss-1] + nums[ss])) / 2
偷的懒必须加回来，因为是两个有序的数组，自己实现一下归并排序吧（此时快排时间复杂度由nlog2n变成了n2，实际测试1k+ms，就不贴了）
"""归并
7:02 PM info
解答成功:
执行耗时:40 ms,击败了62.20% 的Python用户
内存消耗:13.1 MB,击败了86.29% 的Python用户
"""
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
l_index, r_index, merger = 0, 0, []
while l_index < len(nums1) and r_index < len(nums2):
if nums1[l_index] <= nums2[r_index]:
merger.append(nums1[l_index])
l_index += 1
else:
merger.append(nums2[r_index])
r_index += 1
merger = merger + nums1[l_index:] + nums2[r_index:]
ss = len(merger) // 2
ee = len(merger) % 2
if ee:
return merger[ss]
return float((merger[ss-1] + merger[ss])) / 2
