題目描述：

給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。

請你找出這兩個有序數(shù)組的中位數(shù)，并且要求算法的時間復雜度為 O(log(m + n))。

?

方法一：根據(jù)定義，合并、排序以后取中位數(shù)（時間復雜度不符合要求）
這應該是最簡單直接的做法，即根據(jù)定義來做。考慮如下兩種情況：
情況 1：如果合并以后的數(shù)組的長度是偶數(shù)，中位數(shù)有 2 個，此時取它們的平均值；
情況 2：如果合并以后的數(shù)組的長度是奇數(shù)；中位數(shù)有 1 個，把這個值返回即可。
說明：這個解法雖然不符合題目要求，但是是常規(guī)思路。并且它的優(yōu)點也很顯著：即在輸入數(shù)組不是有序數(shù)組的時候，這個算法依然有效，因此如果這一題出現(xiàn)在面試中，向面試官提到這個最簡單的思路，我覺得也是有必要的（一定要把它的這個優(yōu)點連帶說出來）。代碼如下

from typing import Listclass Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:m = len(nums1)n = len(nums2)nums1.extend(nums2)nums1.sort()if (m + n) & 1:return nums1[(m + n - 1) >> 1]#右移一位相當于除以2作者這樣做的目的是為了防止數(shù)據(jù)溢出，但是python好像不存在溢出else:return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2

這段代碼是基于二分查找的歸并排序算法。

將兩個數(shù)據(jù)合并后找到一條線將數(shù)組一分為二，假設數(shù)組1左邊元素的個數(shù)是i，數(shù)組1右邊元素的個數(shù)為j。i和j滿足以下關系式：

j=m+n+1/2 ?? - i其中m和n分別數(shù)組1和數(shù)組2的元素個數(shù)。則只需從數(shù)組1中查找到索引i即可。

在查找過程中主要有以下兩種情況

(1)mums2[j-1]>nums1[i]即數(shù)組2右邊的最小值比數(shù)組1左邊的最大值還要大，此時需要擴大數(shù)組1的左半部分即i+1

(2)mums1[i-1]>nums2[j]即數(shù)組1左邊的最大值比數(shù)組2右邊的最小值還要大，此時需要縮小數(shù)組1的左半部分即i不讓i-1是為了防止數(shù)組越界

from typing import Listclass Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# 為了讓搜索范圍更小，我們始終讓 num1 是那個更短的數(shù)組，PPT 第 9 張if len(nums1) > len(nums2):# 這里使用了 pythonic 的寫法，即只有在 Python，中可以這樣寫# 在一般的編程語言中，得使用一個額外變量，通過"循環(huán)賦值"的方式完成兩個變量的地址的交換nums1, nums2 = nums2, nums1# 上述交換保證了 m <= n，在更短的區(qū)間 [0, m] 中搜索，會更快一些m = len(nums1)n = len(nums2)# 使用二分查找算法在數(shù)組 nums1 中搜索一個索引 i，PPT 第 9 張left = 0right = m# 因為 left_total 這個變量會一直用到，因此單獨賦值，表示左邊粉紅色部分一共需要的元素個數(shù)left_total = (m + n + 1) >> 1while left < right:# 嘗試要找的索引，在區(qū)間里完成二分，為了保證語義，這里就不定義成 mid 了# 用加號和右移是安全的做法，即使在溢出的時候都能保證結(jié)果正確，但是 Python 中不存在溢出# 參考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/i = (left + right) >> 1j = left_total - i# 如果 nums1 左邊最大值 > nums2 右邊最小值if nums2[j - 1] > nums1[i]:# 這個分支縮短邊界的原因在 PPT 第 8 張，情況 ①left = i + 1else:# 這個分支縮短邊界的原因在 PPT 第 8 張，情況 ②# 【注意】：不讓它收縮的原因是討論 nums1[i - 1] > nums2[j]，i - 1 在數(shù)組的索引位置，在 i = 0 時越界right = i# 退出循環(huán)的時候，交叉小于等于一定關系成立，那么中位數(shù)就可以從"邊界線"兩邊的數(shù)得到，原因在 PPT 第 2 張、第 3 張i = leftj = left_total - left# 邊界值的特殊取法的原因在 PPT 第 10 張nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]nums1_right_min = float('inf') if i == m else nums1[i]nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]nums2_right_min = float('inf') if j == n else nums2[j]# 已經(jīng)找到解了，分數(shù)組之和是奇數(shù)還是偶數(shù)得到不同的結(jié)果，原因在 PPT 第 2 張if (m + n) & 1:return max(nums1_left_max, nums2_left_max)else:return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2

轉(zhuǎn)自：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/

總結(jié)

以上是生活随笔為你收集整理的leetcode4两数相加的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。