4. 寻找两个正序数组的中位数
难度困难4502
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 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 = [1]
nums2 = []
def findMedianSortedArrays(nums1, nums2):
result = 0
nums3 = []
mid = int((len(nums1) + len(nums2))/2)
t1 = 0
t2 = 0
t = 0
print(mid)
for i in range(mid + 1):
if((t1 < len(nums1)) and (t2 < len(nums2)) and (nums1[t1] < nums2[t2]) ):
nums3.append(nums1[t1])
t1 += 1
elif((t1 < len(nums1)) and (t2 < len(nums2)) and (nums1[t1] >= nums2[t2])):
nums3.append(nums2[t2])
t2 += 1
elif t1 == len(nums1):
nums3.append(nums2[t2])
t2 += 1
elif t2 == len(nums2):
nums3.append(nums1[t1])
t1 += 1
if((mid != 0)and mid == t):
if ((len(nums1) + len(nums2)) % 2 == 1):
result = nums3[t]
else:
result =float((nums3[t] + nums3[t -1])/2)
elif mid == 0 and t == 0:
result = float(nums3[0])
t += 1
return result
print(findMedianSortedArrays(nums1,nums2))
其实时间复杂度不高O（n/2）但是，可能逻辑分析还不够清晰，所以运行时间68ms。
下面是其他的人的解法：
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def findKthElement(arr1,arr2,k):
len1,len2 = len(arr1),len(arr2)
if len1 > len2:
return findKthElement(arr2,arr1,k)
if not arr1:
return arr2[k-1]
if k == 1:
return min(arr1[0],arr2[0])
i,j = min(k//2,len1)-1,min(k//2,len2)-1
if arr1[i] > arr2[j]:
return findKthElement(arr1,arr2[j+1:],k-j-1)
else:
return findKthElement(arr1[i+1:],arr2,k-i-1)
l1,l2 = len(nums1),len(nums2)
left,right = (l1+l2+1)//2,(l1+l2+2)//2
return (findKthElement(nums1,nums2,left)+findKthElement(nums1,nums2,right))/2
