赞
踩
写在前面:在学习算法中我们会学到很多经典的算法,双指针,二分查找等等,但是这只是一种思想,解题时我们可以灵活的运用,也不必局限一种形式,要将学到的东西,转换成自己的东西。
给定两个大小分别为 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
注意本题在力扣中不用返回的数据不用考虑小数位数,系统会自动保留对应的位数
因为这是两个有序数组,在两个有序数组中寻找中位数,可以先考虑将两个数组合并起来,然后找中位数
有序数组的合并比较简单,就是用两个指针分别指向两个数组的开头,依次比较指针指向的数字,较少的数字添加到新数组
,指针加1,然后再重复以上的循环,直至其中一个指针越界。最后将未添加完的数字合并到新数组
中
详细的流程看代码
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: l1 = 0 l2 = 0 r1 = len(nums1) r2 = len(nums2) arr = [] while True: # 循环添加 if l1>r1-1 or l2>r2-1: # 当有一个数组的数据被添加完成,就跳出循环 break if nums1[l1] > nums2[l2]: arr.append(nums2[l2]) l2+=1 else: arr.append(nums1[l1]) l1+=1 # 添加未合并完成的数组 if l1!=r1: arr.extend(nums1[l1:]) elif l2!=r2: arr.extend(nums2[l2:]) # 根据数组长度的奇偶返回不同的值 if (r1+r2)%2==0: return (arr[((r1+r2)//2)-1]+arr[(r1+r2)//2])/2 else: return arr[(r1+r2)//2]
我们能发现上面这个解题方式中,我们使用了额外的一个数组,浪费了内存空间,因为是两个有序数组,目的又是找出中位数,所以我们可以直接找出中位数,而不用进行合并
这个算法也是用了两个指针,使用情况同第一个类似,只不过我们比较大小后不进行合并,就是用应给变量记录比较的次数,直至比较的次数==中位数的位置
,此时我们再根据具体的情况返回具体的值
具体的思路请看代码
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: l1 = 0 l2 = 0 r1 = len(nums1) r2 = len(nums2) number = 0 # 记录次数 f = 0 # 标志数组是奇数还是偶数 # 根据奇偶设置中间的元素位置 if (r1+r2)%2==0: f = 2 mid = (r1+r2)//2 else: f = 1 mid = (r1+r2)//2+1 while True: if l1>r1-1 or l2>r2-1: break if nums1[l1] > nums2[l2]: number+=1 if number == mid: # 当number等于mid的时候就代表此时已经到了中位数的位置 if f==1: # 奇数情况 return nums2[l2] else: # 偶数情况 if l2==r2-1: # 此时l2指向其中nums2的最后一个元素 return (nums2[l2]+nums1[l1])/2 else: # 返回两种情况中最小的 return min(nums2[l2]+nums2[l2+1],nums2[l2]+nums1[l1])/2 l2+=1 else: # 同上思想一样,对象更换了一下 number+=1 if number == mid: if f==1: return nums1[l1] else: if l1==r1-1: return (nums2[l2]+nums1[l1])/2 else: return min(nums1[l1]+nums1[l1+1],nums2[l2]+nums1[l1])/2 l1+=1 # 这种是当一个数组特别长,中位数在其中一个数组中的情况 if l1!=r1: if f==1: return nums1[mid-l2-1] else: return (nums1[mid-l2-1]+nums1[mid-l2])/2 elif l2!=r2: if f==1: return nums2[mid-l1-1] else: return (nums2[mid-l1-1]+nums2[mid-l1])/2
此时我们能够发现上面的两种解法的时间复杂度不是 O(log (m+n))
,原因就是我们合并和排除数字都是一个一个的进行的 时间复杂度为 O(m+n)
想要实现O(log (m+n))
的时间复杂度,我们可以回想一下什么情况出现log
,二分法
,此时我们的思路就明朗了,解题需要使用二分的思想
,每次排除的数字,都应该是原数据的二分之一
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1) > len(nums2): # 保证数组nums1是较短的哪一个 return self.findMedianSortedArrays(nums2, nums1) infinty = 10*6+1 # m, n = len(nums1), len(nums2) left, right = 0, m # 只需要记录记录第一个数组的指针,第二个数组可以计算出来 # median1:前一部分的最大值 # median2:后一部分的最小值 median1, median2 = 0, 0 while left <= right: # 循环条件 # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1] # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1] i = (left + right) // 2 # 通过计算确定二分后的中间位置 nums1 j = (m + n + 1) // 2 - i # 根据规则计算nums2的需要分的位置 # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j] # 四个数字 看数字是否符合条件 nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 当i为0时 nums_i = (infinty if i == m else nums1[i]) nums_jm1 = (-infinty if j == 0 else nums2[j - 1]) # 当j为0时 nums_j = (infinty if j == n else nums2[j]) if nums_im1 <= nums_j: # 满足这个条件的median1, median2 不一定时最后结果,但是最后结果一定满足这个条件 # 当出现最后结果 left将不在改变,直至循环结束 median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j) # 取分割线左侧的最大值,取分割线右侧的最小值 left = i + 1 else: right = i - 1 # 根据奇偶的不同返回不同的结果 return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1
最后一个我自己的代码太罗嗦了,就使用的是力扣官方的代码。
具体的讲解请大家移步力扣官方
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。