1型檀、題目
給定兩個大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 听盖。算法的時間復雜度應該為 O(log (m+n)) 胀溺。
示例 1：
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2
2皆看、代碼
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
用于找到兩個已排序數(shù)組的第k小的數(shù)仓坞。它通過比較兩個數(shù)組的第k/2個元素來實現(xiàn)這個功能。
如果數(shù)組1的第k/2個元素小于數(shù)組2的第k/2個元素腰吟，那么數(shù)組1的前k/2個元素一定不會是第k小的數(shù)无埃，所以可以將它們排除在外。反之亦然毛雇。這個過程會一直持續(xù)到k等于1或者其中一個數(shù)組為空嫉称。
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
- 這里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
- 取 pivot = min(pivot1, pivot2)灵疮，兩個數(shù)組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
- 這樣 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1织阅，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"始藕，剩下的作為新的 nums1 數(shù)組
- 如果 pivot = pivot2蒲稳，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素氮趋。把這些元素全部 "刪除"伍派，剩下的作為新的 nums2 數(shù)組
- 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要薪），因此需要修改 k 的值诉植，減去刪除的數(shù)的個數(shù)
"""
m,n=len(nums1),len(nums2)
totalLength=m+n
def getKthElement(k):#找到第k個小的元素
index1,index2=0,0
while True:
#特殊情況
if index1==m:
return nums2[index2+k-1]
if index2==n:
return nums1[index1+k-1]
if k==1:
return min(nums1[index1],nums2[index2])
#正常情況
newIndex1=min(index1+k//2-1,m-1)
newIndex2=min(index2+k//2-1,n-1)
pivot1,pivot2=nums1[newIndex1],nums2[newIndex2]
if pivot1<=pivot2:#說明中位數(shù)位于nums1的右半部分和num2的左半部分祥国，因此舍棄num1的左半部分和Num2的右半部分
k-=newIndex1-index1+1#舍去nums1的左半部分刪除的元素
index1=newIndex1+1
else:
k-=newIndex2-index2+1
index2=newIndex2+1
if totalLength%2==1:
return getKthElement((totalLength+1)//2)
else:
return(float(getKthElement(totalLength//2))+float(getKthElement(totalLength//2+1)))/2
3、示例
s=Solution()
nums1=[1,2];nums2 = [3,4]
res=s.findMedianSortedArrays(nums1,nums2)
print(res)
