Daily coding:寻找两个正序数组的中位数
程序员文章站
2022-05-28 14:47:10
...
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
代码1:
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
# 1. 下面这些情况进行处理
len1 = len(nums1)
len2 = len(nums2)
# 一个数组为空,补上另一个数组,中值/2后还是原来的结果(类似于: 3 * 2 / 2还是原来的结果)
if len1 == 0: nums1 = nums2
elif len2 == 0: nums2 = nums1
if len1 == 1 and len2 == 1: return (nums1[0] + nums2[0]) / 2 # 这个情况直接返回
# 2. 获取基本变量信息
lenAll = len1 + len2
mid = int(lenAll / 2 + 1) # 使运行到这里长度总>=3,mid中值的位置(3/2+1=2、4/2+1=3)
i = j = 0 # 便利索引
ary = [0, 0] # 存储中值的列表
# 3. 核心代码
while i < len1 and j < len2:
# 假定两个数字长度相同,和一个数组遍历到临界点的时候,刚好i + j == mid
if nums1[i] < nums2[j]:
ary[(i + j) % 2] = nums1[i]
i += 1
else:
ary[(i + j) % 2] = nums2[j]
j += 1
if i + j == mid: break # 达到中值 退出循环
# 对两个数组长度不一,以及一个数组下标i或j先行达临界点(nums1.length = i或nums2.length == j)进行补充
while i + j < mid and i == len1:
ary[(i + j) % 2] = nums2[j]
j += 1
while i + j < mid and j == len2:
ary[(i + j) % 2] = nums1[i]
i += 1
# 4. 判断后返回对应的运行结果
if lenAll % 2 != 0:
return ary[(i + j - 1) % 2] # 总长度为奇数,最后一个赋值就是中值。
else:
return (ary[0] + ary[1]) / 2 # 总长度为偶数,直接返回他们相加的平均值。
代码2:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1.sort()
length=len(nums1)
if length%2==1:
return nums1[length//2]
else:
return (nums1[length//2]+nums1[length//2-1])/2
上一篇: mac打开ipynb文件
下一篇: Daily coding:寻找重复数