"""给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 = [1, 3]
nums2 = [2]则中位数是 2.0
示例 2:nums1 = [1, 2]
nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
"""
from typing import List
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""Merge two arrays to get the median, O((m+n)/2)Algorithm: Find k-th element in 2 arrayA: A_left A[m/2] A_rightB: B_left B[n/2] A_rightif A[m/2]>B[n/2] and k>m/2+n/2, then disregard B_left and B[n/2]if A[m/2]>B[n/2] and k<=m/2+n/2, then disregard A_right and A[m/2]if A[m/2]<=B[n/2] and k>m/2+n/2, then disregard A_left and A[m/2]if A[m/2]<=B[n/2] and k<=m/2+n/2, then disregard B_right and B[n/2]whether to disregard A[m/2] or B[n/2] takes time to considerT(N) = T(3/4 N) + O(1), thus T(N) = O(lg N) where N = |A|+|B|O(log (m+n)), thus binary search.:param A: list:param B: list:return: float"""m = len(nums1)n = len(nums2)if (m+n) % 2 == 0:return (self.find_kth(nums1,nums2,(m+n)//2) + self.find_kth(nums1,nums2,(m+n)//2-1)) / 2.0else:return self.find_kth(nums1,nums2,(m+n) // 2)def find_kth(self,arr1,arr2,num):if not arr1:return arr2[num]if not arr2:return arr1[num]if num == 0:return min(arr1[0],arr2[0])m,n = len(arr1),len(arr2)if arr1[m//2] >= arr2[n//2]:if num > m//2 + n // 2:return self.find_kth(arr1,arr2[n//2+1:],num-n//2 -1)else:return self.find_kth(arr1[:m//2],arr2,num)else:return self.find_kth(arr2,arr1,num)