4.尋找兩個正序數組的中位數
給定兩個大小分别為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并傳回這兩個正序數組的 中位數 。
示例 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
二分查找
直接求中位數可能不好想到，那麼我們換個思路.假設有下面兩個數組 A 和 B，A數組的長度是4，B數組的長度是8。
意境級講解二分查找算法、python
如上圖，因為A+B的總長度是12，是偶數，是以求中位數的話，需要找到第6小、第7小的元素，找到這兩個元素後，相加再 / 2 就可以了。
這裡是偶數長度的情況，如果是兩個數組長度相加後是奇數也是類似的，比如總長度是 13 ，那就需要找第7小的元素。
是以，這題可以轉化為，如何找到第k小的元素。
- 如果總長度N是偶數，則需要找到兩個數組中第
N / 2
N / 2 + 1
- 如果總長度N是奇數，則需要找到兩個數組中第
N / 2 + 1
題目限制了時間複雜度，是以這裡找第k小的過程，肯定也是二分的方式。
假設兩個有序數組分别是 A \mathrm{A} A 和 B \mathrm{B} B 。要找到第 k k k 個元素，我們可以比較 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1], 其 中 / / / 表示整數除法。由于 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 的前面分别有 A [ 0 … k / 2 − 2 ] \mathrm{A}[0 \ldots k / 2-2] A[0…k/2−2] 和 B [ 0.. k / 2 − 2 ] \mathrm{B}[0 . . k / 2-2] B[0..k/2−2], 即 k / 2 − 1 k / 2-1 k/2−1 個元素, 對于 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 中的較小值，最多隻會有 ( k / 2 − 1 ) + ( k / 2 − (k / 2-1)+(k / 2- (k/2−1)+(k/2− 1) ≤ k − 2 \leq k-2 ≤k−2 個元素比它小，那麼它就不能是第 k k k 小的數了。
是以我們可以歸納出三種情況：
- 如果 A [ k / 2 − 1 ] < B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]<\mathrm{B}[k / 2-1] A[k/2−1]<B[k/2−1], 則比 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 小的數最多隻有 A \mathrm{A} A 的前 k / 2 − 1 k / 2-1 k/2−1 個數和 B \mathrm{B} B 的 前 k / 2 − 1 k / 2-1 k/2−1 個數, 即比 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 小的數最多隻有 k − 2 k-2 k−2 個， 是以 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 不可能是第 k k k 個 數, A [ 0 ] \mathrm{A}[0] A[0] 到 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 也都不可能是第 k k k 個數, 可以全部排除。
- 如果 A [ k / 2 − 1 ] > B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]>\mathrm{B}[k / 2-1] A[k/2−1]>B[k/2−1], 則可以排除 B [ 0 ] \mathrm{B}[0] B[0] 到 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 。
- 如果 A [ k / 2 − 1 ] = B [ k / 2 − 1 ] \mathrm{A}[k / 2-1]=\mathrm{B}[k / 2-1] A[k/2−1]=B[k/2−1], 則可以歸入第一種情況處理。
可以看到，比較 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 和 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 之後，可以排除 k / 2 k / 2 k/2 個不可能是第 k k k 小的數， 查找範圍縮 小了一半。同時，我們将在排除後的新數組上繼續進行二分查找，并且根據我們排除數的個數，減 少 k k k 的值，這是因為我們排除的數都不大于第 k k k 小的數。有以下三種情況需要特殊處理：
- 如果 A [ k / 2 − 1 ] \mathrm{A}[k / 2-1] A[k/2−1] 或者 B [ k / 2 − 1 ] \mathrm{B}[k / 2-1] B[k/2−1] 越界，那麼我們可以選取對應數組中的最後一個元素。在這 種情況下，我們必須根據排除數的個數減少 k k k 的值，而不能直接将 k k k 減去 k / 2 k / 2 k/2 。
- 如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接傳回另一個數組中第 k k k 小的元素。
- 如果 k = 1 k=1 k=1, 我們隻要傳回兩個數組首元素的最小值即可。
因為數組A、數組B都是有序的，是以我們需要利用這個有用的特性，每次縮小查找範圍:第一次找 k 小、第二次就是找 k/2 小、然後是 k/4小，直到 k 等于1時。
還是以上面的數組為例，A數組為
[1,2,4,9]
，B數組是
[1,2,3,4,5,6,7,8]
. 我們需要找第6、第7小的元素，假設我們先找第6小的元素，也就是k = 6。要找到第 k k k 個元素，我們可以比較 A [ k / 2 − 1 ] \text{A}[k/2-1] A[k/2−1]和 B [ k / 2 − 1 ] \text{B}[k/2-1] B[k/2−1]
我們首先比較 A數組中第3個元素，B數組中第3個元素，也就是
A[k/2-1]
和
B[k/2-1]
，如下圖：
由于A[k/2-1] > B[k/2-1]，這時候我們就可以忽略掉一些元素了。
上圖中 A數組中的4，它前面有2個元素，也就是
k/2-1
個元素，B數組的3，它前面也有2個元素，也就是
k/2-1
個元素，一共有
k-2
個元素
假設 B數組的
3
，也就是B[k/2-1] 比這
k-2
個元素都大。這樣的話，我們就可以排除一些元素了，
既然B[k/2-1]都不是第k小的元素，那麼 B[k/2-1]前面的那些更不是了，于是我們将B[0]、B[1]、B[2]。。。B[k/2-1]這些元素全部忽略掉。
當我們忽略掉 B數組中的元素後， k也要跟着減小，
k- k//2=3
。這個解法的整體求解過程，就是不斷縮小數組的規模，同時把k也跟着縮小。如下圖
這次 k=3，
k//2-1=0
,是以A[k/2-1]對應的就是A[0],B[k/2-1]對應是B[3]，因為我們之前忽略掉了 B數組中的前3個元素，是以B數組的第1個元素是從下标3開始的。 如下圖橙色為
k//2-1
：
經過這次比較後，
A[k/2-1] < B[k/2-1]
，是以忽略掉
A[0]
，然後将 k 變成
k- k//2=2
。
k此時等于2，
k//2-1=0
,于是
A[k/2-1]
對應的是
A[1]
，因為剛才已經忽略掉
A[0]
了,
B[k/2-1]
對應的是
B[3]
,如下圖：
經過這次比較後，
A[k/2-1] < B[k/2-1]
，是以忽略掉
A[1]
，然後将 k 變成
k- k//2=1
。
當k==1時，傳回A數組中第一個元素 和 B數組中第一個元素的較小者。
此時A數組中的第1個元素是A[2]，B數組中第1個元素是B[3]，即求
min(A[2],B[3])
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
def getKthElement(k):
"""
- 主要思路：要找到第 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),兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
- 這樣 pivot 本身最大也隻能是第 k-1 小的元素
- 如果 pivot = pivot1,那麼 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "删除",剩下的作為新的 nums1 數組
- 如果 pivot = pivot2,那麼 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "删除",剩下的作為新的 nums2 數組
- 由于我們 "删除" 了一些元素（這些元素都比第 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])
# 正常情況,index1,index2作為起始點,newindex1,newindex2作為比較點 在不停的更新
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: # <=将兩種情況合并
k -= newIndex1 - index1 + 1 # 兩者相減後+1,這才是真正減去的長度
index1 = newIndex1 + 1 # 連同比較位置也一同删去了,是以新的開始是 比較位置 的後一位
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
totalLength = m + n
if totalLength % 2 == 1: # 可以将兩種情況合并,奇數會求兩次同樣的k
return getKthElement((totalLength + 1) // 2)
else:
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""主要思路：要找到第 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 個
"""
total = len(nums1) + len(nums2)
# 如果A數組長度+B數組長度total是奇數，則找total/2+1小的元素
# 即為中位數
if total % 2 == 1:
midIndex = total // 2 + 1
res = self.getKthElement(nums1, nums2, midIndex)
return float(res)
# 否則，找total/2，total/2+1這兩個元素
else:
midIndex_1 = total // 2
midIndex_2 = total // 2 + 1
a = self.getKthElement(nums1, nums2, midIndex_1)
b = self.getKthElement(nums1, nums2, midIndex_2)
return (a + b) / 2.0
def getKthElement(self,nums1, nums2, k):
len1 = len(nums1)
len2 = len(nums2)
index1 = 0
index2 = 0
while True:
# 邊界情況，當index1越界時，直接傳回nums2的第k小元素
if index1 == len1:
return nums2[index2 + k -1]
# 邊界情況，當index2越界時，直接傳回nums1的第k小元素
if index2 == len2:
return nums1[index1 + k - 1]
# 邊界情況，k等于1時，傳回nums1第一個元素和nums2第一個元素較小者
if k == 1:
return min(nums1[index1], nums2[index2])
new_index1 = min(index1 + k // 2- 1 , len1- 1 )
new_index2 = min(index2 + k // 2 - 1, len2 - 1)
pivot1 = nums1[new_index1]
pivot2 = nums2[new_index2]
# 比較nums1[k/2-1]和nums2[k/2-1]
# 如果nums1的小，則忽略掉nums1[0] - nums1[k/2-1]這些元素
# 再更新 k，k 要減去忽略掉的那些元素，index1也要更新，待下輪使用
if pivot1 <= pivot2:
k -= (new_index1 - index1 + 1)
index1 = new_index1 + 1
# 如果nums2的小，則忽略掉nums2[0] - nums2[k/2-1]這些元素
# 再更新 k，k 要減去忽略掉的那些元素，index2也要更新，待下輪使用
else:
k -= (new_index2 - index2 + 1)
index2 = new_index2 + 1
複雜度分析
- 時間複雜度： O ( log ( m + n ) ) O(\log (m+n)) O(log(m+n)), 其中 m m m 和 n n n 分别是數組 n u m s 1 nums_{1} nums1 和 n u m s 2 n u m s_{2} nums2 的長度。初始時有 k = ( m + n ) / 2 k=(m+n) / 2 k=(m+n)/2 或 k = ( m + n ) / 2 + 1 k=(m+n) / 2+1 k=(m+n)/2+1, 每一輪循環可以将查找範圍減少一半， 是以時間複雜度 是 O ( log ( m + n ) ) O(\log (m+n)) O(log(m+n)) 。
- 空間複雜度：O(1)。
劃分數組
為了使用劃分的方法解決這個問題，需要了解「中位數的作用是什麼」。在統計中，中位數被用來：
将一個集合劃分為兩個長度相等的子集，其中一個子集中的元素總是大于另一個子集中的元素。
如果了解了中位數的劃分作用，就很接近答案了。
首先，在任意位置 i i i 将 A \text{A} A 劃分成兩個部分：
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于 A \mathrm{A} A 中有 m m m 個元素， 是以有 m + 1 m+1 m+1 種劃分的方法 ( i ∈ [ 0 , m ] ) (i \in[0, m]) (i∈[0,m]) 。
l e n ( l e f t A ) = i , l e n ( r i g h t A ) = m − i len(left_A)=i,len(right_A)=m−i len(leftA)=i,len(rightA)=m−i.
注意：當 i = 0 i=0 i=0 時，left_A 為空集， 而當 i = m i=m i=m 時, right_A 為空集。
采用同樣的方式，在任意位置 j j j 将 B \text{B} B 劃分成兩個部分：
left_B | right_B
B[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_part
A[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 \mathrm{A} A 和 B \mathrm{B} B 的總長度是偶數時，如果可以确認：
- len(left_part) = = = len(right_part) :
i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
- max(left_part ) ≤ min ( ) \leq \min ( )≤min( right_part ) ) )
max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
- 那麼， { A , B } \{\mathrm{A}, \mathrm{B}\} {A,B} 中的所有元素已經被劃分為相同長度的兩個部分，且前一部分中的元素總是小于或等 于後一部分中的元素。中位數就是前一部分的最大值和後一部分的最小值的平均值:
median = max ( left_part ) + min ( right_part ) 2 （ m a x ( A [ i − 1 ] , B [ j − 1 ] ） + m i n ( A [ i ] , B [ j ] ） ） / 2 \text { median }=\frac{\max (\text { left\_part })+\min (\text { right\_part })}{2}\\ （max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2 median =2max( left_part )+min( right_part )（max(A[i−1],B[j−1]）+min(A[i],B[j]））/2
當 A \mathrm{A} A 和 B 的總長度是奇數時，如果可以确認：
- len(left_part ) = )= )= len(right_part) + 1 +1 +1
i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
- max(left_part ) ≤ min ( ) \leq \min ( )≤min( right_part ) ) )
- 那麼, { A , B } \{\mathrm{A}, \mathrm{B}\} {A,B} 中的所有元素已經被劃分為兩個部分，前一部分比後一部分多一個元素, 且前一部分 中的元素總是小于或等于後一部分中的元素。中位數就是前一部分的最大值:
median = max ( left_part ) m a x ( A [ i − 1 ] , B [ j − 1 ] ） \text { median }=\max (\text { left\_part })\\ max ( A [ i - 1 ] , B [ j - 1 ]） median =max( left_part )max(A[i−1],B[j−1]）
第一個條件對于總長度是偶數和奇數的情況有所不同，但是可以将兩種情況合并。
i + j = m + n + 1 2 i+j=\frac{m+n+1}{2} i+j=2m+n+1
第二個條件對于 總長度是偶數和奇數的情況是一樣的。
要確定這兩個條件，隻需要保證：
- 0 ≤ i ≤ m , 0 ≤ j ≤ n 0 \leq i \leq m, 0 \leq j \leq n 0≤i≤m,0≤j≤n 。 如果我們規定 A \mathrm{A} A 的長度小于等于 B \mathrm{B} B 的長度， 即 m ≤ n ∘ m \leq n_{\circ} m≤n∘ 這樣對于任意的 i ∈ [ 0 , m ] i \in[0, m] i∈[0,m], 都有 j = m + n + 1 2 − i ∈ [ 0 , n ] j=\frac{m+n+1}{2}-i \in[0, n] j=2m+n+1−i∈[0,n], 那麼我們在 [ 0 , m ] [0, m] [0,m] 的範圍内枚舉 i i i 并得到 j j j, 就 不需要額外的性質了。
- 如果 m > n m>n m>n, 那麼得出的 j j j 有可能是負數。那麼我們隻要交換 A \mathrm{A} A 和 B 即可。
為了保證
max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
,因為 A 數組和 B 數組是有序的，是以 B [ j − 1 ] ≤ A [ i ] \mathrm{B}[j-1] \leq \mathrm{A}[i] B[j−1]≤A[i] 以及 A [ i − 1 ] ≤ B [ j ] , \mathrm{A}[i-1] \leq \mathrm{B}[j], \quad A[i−1]≤B[j], 即前一部分的最大值小于等于後一部分的最小值。
為了簡化分析，假設 A [ i − 1 ] , B [ j − 1 ] , A [ i ] , B [ j ] \mathrm{A}[i-1], \mathrm{B}[j-1], \mathrm{A}[i], \mathrm{B}[j] A[i−1],B[j−1],A[i],B[j] 總是存在。對于 i = 0 , i = m , j = 0 、 j = n i=0, i=m, j=0 、 j=n i=0,i=m,j=0、j=n 這樣 的臨界條件，我們隻需要規定 A [ − 1 ] = B [ − 1 ] = − ∞ , A [ m ] = B [ n ] = ∞ \mathrm{A}[-1]=\mathrm{B}[-1]=-\infty, A[m]=\mathrm{B}[n]=\infty A[−1]=B[−1]=−∞,A[m]=B[n]=∞ 即可。這也是比較直覺 的：當一個數組不出現在前一部分時，對應的值為負無窮，就不會對前一部分的最大值産生影響; 當一個數組不出現在後一部分時，對應的值為正無窮，就不會對後一部分的最小值産生影響。
是以我們需要做的是：
在 [ 0 , m ] [0, m] [0,m] 中找到 i i i, 使得：
B [ j − 1 ] ≤ A [ i ] \mathrm{B}[j-1] \leq \mathrm{A}[i] B[j−1]≤A[i] 且 A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j], 其中 j = m + n + 1 2 − i j=\frac{m+n+1}{2}-i j=2m+n+1−i
我們證明它等價于：
在 [ 0 , m ] [0, m] [0,m] 中找到最大的 i i i, 使得:
A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j], 其中 j = m + n + 1 2 − i j=\frac{m+n+1}{2}-i j=2m+n+1−i
這是因為:
- 當 i i i 從 0 ∼ m 0 \sim m 0∼m 遞增時, A [ i − 1 ] \mathrm{A}[i-1] A[i−1] 遞增, B [ j ] \mathrm{B}[j] B[j] 遞減，是以一定存在一個最大的 i i i 滿足 A [ i − 1 ] ≤ \mathrm{A}[i-1] \leq A[i−1]≤ B [ j ] \mathrm{B}[j] B[j]
- 如果 i i i 是最大的， 那麼說明 i + 1 i+1 i+1 不滿足。将 i + 1 i+1 i+1 帶入可以得到 A [ i ] > B [ j − 1 ] \mathrm{A}[i]>\mathrm{B}[j-1] A[i]>B[j−1], 也就是 B [ j − 1 ] < A [ i ] \mathrm{B}[j-1]<\mathrm{A}[i] B[j−1]<A[i], 就和我們進行等價變換前 i i i 的性質一緻了（甚至還要更強）。
是以我們可以對 i i i 在 [ 0 , m ] [0, m] [0,m] 的區間上進行二分搜尋，找到最大的滿足 A [ i − 1 ] ≤ B [ j ] \mathrm{A}[i-1] \leq \mathrm{B}[j] A[i−1]≤B[j] 的 i i i 值，就得 到了劃分的方法。此時，劃分前一部分元素中的最大值，以及劃分後一部分元素中的最小值，才可 能作為就是這兩個數組的中位數。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
infinty = 2**40
m, n = len(nums1), len(nums2)
left, right = 0, m
# median1：前一部分的最大值
# median2：後一部分的最小值
median1, median2 = 0, 0
while left <= right:
# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
# // 後一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
i = (left + right) // 2
j = (m + n + 1) // 2 - i
# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
# 當一個數組不出現在前一部分時,對應的值為負無窮,就不會對前一部分的最大值産生影響
nums_im1 = (-infinty if i ==0 else nums1[i - 1])
nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
# 當一個數組不出現在後一部分時,對應的值為正無窮,就不會對後一部分的最小值産生影響
nums_i = (infinty if i == m else nums1[i])
nums_j = (infinty if j == n else nums2[j])
if nums_im1 < nums_j:
median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
left = i + 1
else:
right = i - 1
return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1
- 時間複雜度： O ( log min ( m , n ) ) ) O(\log \min (m, n))) O(logmin(m,n))), 其中 m m m 和 n n n 分别是數組 n u m s 1 n u m s_{1} nums1 和 n u m s 2 n u m s_{2} nums2 的長度。查找的區 間是 [ 0 , m ] [0, m] [0,m], 而該區間的長度在每次循環之後都會減少為原來的一半。是以，隻需要執行 log m \log m logm 次循環。由于每次循環中的操作次數是常數，是以時間複雜度為 O ( log m ) O(\log m) O(logm) 。 由于我們可 能需要交換 n u m s 1 n u m s_{1} nums1 和 n u m s 2 n u m s_{2} nums2 使得 m ≤ n m \leq n m≤n, 是以時間複雜度是 O ( log min ( m , n ) ) ) \left.O(\log \min (m, n))\right) O(logmin(m,n))) 。
- 空間複雜度：O(1)。
參考
力扣（LeetCode） (leetcode-cn.com)