python-leetcode 67.寻找两个正序数组中的中位数

题目：

给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请找出并返回这两个正序数组的中位数。

---

通过双指针和二分查找的思想，找到两个有序数组的中位数。

1.初始化和基本情况处理

首先获取两个个数组的长度m和n,计算总长度total=m+n

定义一个辅助函数，用于找到两个数组合并后的第k小的元素

2.寻找第k小的元素

使用双指针i和j分别遍历nums[i]和nums[j]

边界条件处理：

如果i到达nums1的末尾，返回nums2中从j开始的第k个元素

如果j到达nums2的末尾，则返回nums1中从i开始的第k个元素。

如果k==1,则返回nums[i]和nums[j]中较小的值

二分查找：

计算mid=k//2,并确定两个数组中的比较位置new_i和new_j

比较nums1[new_i]和nums2[new_j],如果nums1[new_i]<=nums2[new_j],说明nums1的前mid个元素可以排除，他们不可能是第k小的元素，因此更新，i和j

否则，排除nums2的前mid个元素，更新j和k

3.计算中位数

奇数长度：如果total是奇数，直接返回第total+1//2小的元素

偶数长度：如果total是偶数，就返回第total//2和total.//2+1的平均值

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""m,n=len(nums1),len(nums2) #计算两个数组的长度total=m+n  #两个数组长度的总和def findKthElement(k): #在两个有序数组中找到第 k 小的元素i,j=0,0  #初始化两个指针i和j，分别用于跟踪nums1和nums2 的当前位置while True:if i==m:return nums2[j+k-1]#如果nums1已经全部被排除i == m，则k小的元素在nums2 中，位置是j + k - 1if j==n:return nums1[i+k-1]#如果nums2已经全部被排除j == n，则 k小的元素在 nums1 中，位置是i + k - 1if k==1:  # k 减到 1，说明要找最小的元素return min(nums1[i],nums2[j])mid=k//2  #当前 k 的一半new_i=min(i+mid-1,m-1)#ew_i 是 nums1 中从当前位置 i 开始，向后移动 mid-1 个位置，但不能超过数组长度new_j=min(j+mid-1,n-1)   #同理if nums1[new_i]<=nums2[new_j]: #nums1的前new_i - i + 1 个元素可以安全排除k-=new_i-i+1  #减去排除的元素数量i=new_i+1else:k-=new_j-j+1 #排除 nums2 的前 new_j - j + 1 个元素j=new_j+1if total%2==1: #合并后数组长度是奇数，直接返回中间的那个元素（第 (total+1)/2 小的元素）return findKthElement((total+1)//2)else:  #合并后数组长度是偶数，返回中间两个元素的平均值left=findKthElement(total//2)right=findKthElement(total//2+1)return (left+right)/2.0

时间复杂度：O(log(min,m,n))).每次k会减半

空间复杂度：O(1)