Title

給定兩個大小為 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

Solve

暴力

虧我一開始還想著用歸并呢，結果直接合并→排序→判斷就能AC，兩行代碼解決戰斗。

def findMedianSortedArrays_violence(self, nums1: List[int], nums2: List[int]) -> float:nums3 = sorted(nums1 + nums2)return nums3[int(len(nums3) / 2)] if len(nums3) % 2 else (nums3[int(len(nums3) / 2)] + nums3[int(len(nums3) / 2 - 1)]) / 2

劃分數組

暴力的方法畢竟沒有什么技術含量，還是得搞一搞牛掰格拉斯的算法。

在統計中，中位數被用來：將一個集合劃分為兩個長度相等的子集，其中一個子集中的元素總是大于另一個子集中的元素。

首先，在任意位置i將A劃分成兩個部分：

left_A i right_AA[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]

由于A中有m個元素，所以有m+1種劃分的方法(i∈[0,m])。

len(left_A)=i len(right_A)=m?i

當i=0時，left_A為空集，當i=m時，right_A為空集。

采用同樣的方式，在任意位置j將B劃分成兩個部分：

left_B j right_BB[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]

將left_A和left_B放入一個集合，將right_A和right_B放入另一個集合，再把這兩個新的集合分別命令為left_part和right_part：

left_part | right_partA[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]

---

當A和B的總長度是偶數時，如果可以確定：

len(left_part)=len(right_part)

max(left_part)<=min(right_part)

那么，{A,B}中的所有元素已經被劃分成相同長度的兩個部分，left_part中的元素總是小于或等于right_part中的元素，中位數就是left_part的最大值和right_part的最小值的平均值：
$$median=\frac{max(left\_part)+min(right\_part)}{2}$$

---

當A和B的總長度是奇數時，如果可以確定：

len(left_part)=len(right_part)+1

max(left_part)<=min(right_part)

那么，{A,B}中的所有元素已經被劃分成兩個部分，left_part比right_part多一個元素，并且left_part中的元素總是小于或等于right_part中的元素，中位數就是left_part的最大值：
$$median=max(left\_part)$$

---

第一個條件對于總長度是偶數和奇數的情況有所不同，但是可以將兩種情況合并。

第二個條件對于總長度是偶數和奇數的情況是一樣的。

要確保這兩個條件，只需要保證：

i+j=m?i+n?j（當 m+n 為偶數）或 i + j = m - i + n - j + 1（當 m+n 為奇數）。等號左側為left_part的元素個數，等號右側為right_part的元素個數。整理可得：
$$i+j=int(\frac{m+n+1}{2})$$

0<=i<=m,0<=j<=n。規定len(A)<=len(B)，即m<=n，否則交換A和B，這樣對于任意的i∈[0,m]，都有$$j=\frac{m+n+1}{2}?i\in [0,n]$$此時我們在[0,m]的范圍內枚舉i即可通過計算得到j。

B[j-1]<=A[i]以及A[i-1]<=B[j]，即left_part的最大值小于等于right_part的最小值。

為了簡化分析，假設A[i?1],B[j?1],A[i],B[j]總是存在，對于 i=0、i=m、j=0、j=n 這樣的臨界條件，規定 A[?1]=B[?1]=?∞，A[m]=B[n]=∞ 即可。

這也是比較直觀的：當一個數組不出現在left_part時，對應的值為負無窮，就不會對求left_part的最大值產生影響，當一個數組不出現在right_part時，對應的值為正無窮，就不會對求right_part的最小值產生影響。

現在我們需要做的是：在[0,m] 中找到 i，使得：
$$B[j?1]\le A[i]$$$$A[i?1]\le B[j]$$$$j=\frac{m+n+1}{2}?i$$

當i從0~m遞增時，A[i-1]遞增，B[j]遞減，所以一定存在一個最大的i滿足A[i?1]≤B[j]，如果i是最大的，那么說明i+1不滿足。將i+1帶入可以得到A[i]>B[j?1]，因此可以證明它等價于：在[0,m] 中找到 i，使得：
$$A[i?1]\le B[j]$$$$j=\frac{m+n+1}{2}?i$$

我們可以對 i 在 [0, m]的區間上進行二分搜索，找到最大的i滿足A[i?1]≤B[j]，就得到了劃分的方法。

此時，劃分left_part元素中的最大值，以及劃分right_part元素中的最小值，才可能作為這兩個數組中的中位數。

復雜度分析

時間復雜度：O(logmin(m,n)))，其中 m 和 n 分別是數組nums1 和 nums2 的長度。查找的區間是 [0, m]，而該區間的長度在每次循環之后都會減少為原來的一半。所以，只需要執行 logm 次循環。由于每次循環中的操作次數是常數，所以時間復雜度為 O(logm)。由于我們可能需要交換 nums1 和 nums2 使得 m≤n，因此時間復雜度是 O(logmin(m,n)))。

空間復雜度：O(1)。

Code

def findMedianSortedArrays_binary(self, nums1: List[int], nums2: List[int]) -> float:if len(nums1) > len(nums2):return self.findMedianSortedArrays_binary(nums2, nums1)m, n = len(nums1), len(nums2)left, right, maxNumber = 0, m, 2 ** 19maxLeft, minRight = 0, 0while left <= right:i = (left + right) // 2j = (m + n + 1) // 2 - inums_i_1 = -maxNumber if i == 0 else nums1[i - 1]nums_i = maxNumber if i == m else nums1[i]nums_j_1 = -maxNumber if j == 0 else nums2[j - 1]nums_j = maxNumber if j == n else nums2[j]if nums_i_1 <= nums_j:left = i + 1maxLeft, minRight = max(nums_i_1, nums_j_1), min(nums_i, nums_j)else:right = i - 1return (maxLeft + minRight) / 2 if (m + n) % 2 == 0 else maxLeft

總結

以上是生活随笔為你收集整理的4. Median of Two Sorted Arrays的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。