hot100经典：困难 Leetcode 4. 寻找两个正序数组的中位数
描述
给定两个大小分别为 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
思路
转换为找topK问题，由于有两个数组，分别在两边找tok K/2，想法很精妙
代码
使用递归，后续可以优化数组深拷贝带来的时间开销
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:n = len(nums1)m = len(nums2)if((n+m)%2 != 0):return float(self.getTopK((n+m)//2+1,nums1,nums2))else:return (self.getTopK((n+m)//2+1,nums1,nums2) + self.getTopK((n+m)//2,nums1,nums2)) / 2 def getTopK(self,k,arr1,arr2):if(not arr1): return arr2[k-1]if(not arr2): return arr1[k-1]if(k == 1): return min(arr1[0],arr2[0])kk = min(k//2,len(arr1),len(arr2))if(arr1[kk-1] <= arr2[kk-1]):return self.getTopK(k-kk,arr1[kk:],arr2)else:return self.getTopK(k-kk,arr1,arr2[kk:])