写在前面：在学习算法中我们会学到很多经典的算法，双指针，二分查找等等，但是这只是一种思想，解题时我们可以灵活的运用，也不必局限一种形式，要将学到的东西，转换成自己的东西。
题目
给定两个大小分别为 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
最后一个我自己的代码太罗嗦了，就使用的是力扣官方的代码。
具体的讲解请大家移步力扣官方
