求中位數_leetcode算法題4：以O(log (m+n))時間找到兩數組中位數

leetcode算法題4：Median of Two Sorted Arrays

算法題目描述：There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

1. 算法解決過程

1.1.首先需要了解什麼是中位數，中位數用來：

把一個大集合分成兩個長度相等的子集，右邊的子集總是大于左邊的子集 。 如果大集合的長度為偶數，則中位數是中間兩個數的平均數，如果長度為奇數，則中位數則是最中間的那一位數字

1.2.利用

折半查找

的思想，對兩個排序數組進行分割，如A在位置

i

處被分割成兩段，

由于A有

m

個元素，是以分割位置總共有m+1個，（i = 0~m).需要注意，當i=0 時，LeftA為空，當i = m時，RightA為空。分割之後：

len(leftA)= i

len(rightA)=m−i

同理，用相同的方法來分割B，B在

j

處被分割為兩段，

1.3.順序數組A和B都被分割之後，将LeftA和和LeftB放在一起，RightA和RightB放在一起，如下圖所示;

需要保證如下條件，才能求得中位數：

(1) max(LeftPart)<=min(Right_part), B[j-1]<=A[i] && A[i-1]<= B[j] (2) i + j = （m+n+1）/ 2

之是以需要滿足條件(2)是因為:

i + j

是leftPart的長度，

m+n

是集合總長度, 當m+n是偶數時, （m+n+1）/ 2用的是整除（注意python應該用// ),得到的長度是總長度的一半； 當m+n是奇數時,（m+n+1）/ 2用的是整除（注意python應該用// ),得到的長度是總長度的一半再加1;

i + j = （m+n+1）/ 2

保證了

LeftPart的長度等于Right_part或者比RightPart多一個。

可以得到：

j = （m+n+1）/ 2 - i

, 需要注意的是

n>=m

, 因為n如果小于m,當i取m時，j可能會變成負數

1.4.開始求中位數：

(1) 當m+n為偶數時， median= （max(leftPart)+min(rightPart)）/ 2 (2)當m+n為奇數時，由于左邊的數字個數比右邊多一個，是以中位數一定在左邊， median= max(leftPart)

2. 具體算法描述

(1) 設imin = 0, imax = m, 在[imin,imax]中進行折半查找 (2) i = （imin + imax)/2, j = (m+n+1)/2 - i (python中注意用//)

(3) 通過(2)可以确定len(LeftPart) = len(RightPart),或者len(LeftPart)= len(RightPart) + 1。然後需要确定:

max(LeftPart)<=min(RightPart) , 即 max(LeftB)<=min(RightA) && max(LeftA)<=ming(RightB)

有以下三種情況：

1. B[j-1]<=A[i] && A[i-1]<=B[j], 順利找到 i , j 的位置停止搜尋。

2. B[j-1]>A[i], 此時說明A分割的位置太靠左，需要大一點，是以将 i 向右邊移動一步，令imin = i+1, 然後轉到（2）

3. A[i-1]>B[j], 此時說明A分割的位置太靠右，需要小一點，是以将 i 向左邊移動一步，令imax = i-1, 然後轉到（2）

邊界問題考慮

：

當i = 0時，說明LeftPart沒有A的部分，令max(LeftA) = 負無窮；當i = m時，說明RightPart部分沒有A的部分，令min(RightA) = 正無窮。

當j = 0時，說明LeftPart沒有B的部分，令max(LeftB) = 負無窮；當j = n時，說明RightPart部分沒有B的部分，令min(RightB) = 正無窮。

(4) 求出中位數：當m+n為偶數時，median=(max(leftPart)+min(rightPart))/2,

當m+n為奇數時，由于左邊的數字個數比右邊多一個, 是以中位數一定在左邊, median= max(leftPart)

3. python實作代碼

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len_array1 = len(nums1)
        len_array2 = len(nums2)
 if len_array1 > len_array2:
 return self.findMedianSortedArrays(nums2, nums1)
 # 要o(log（m+n)的複雜度，是以要折半查找
        low = 0
        high = len_array1
 while low <= high:
            array1_portion = (low + high) // 2
            array2_portion = (len_array1 + len_array2 + 1) // 2 - array1_portion
 # 兩個數組分别分成兩段之後，分别比較分段點前後數字的大小,需要考慮左邊沒有或者右邊沒有的情況
            maxLeft_array1 = (array1_portion == 0) and -float('inf') or nums1[array1_portion - 1]
            minRight_array1 = (array1_portion == len_array1) and float('inf') or nums1[array1_portion]

            maxLeft_array2 = (array2_portion == 0) and -float('inf') or nums2[array2_portion - 1]
            minRight_array2 = (array2_portion == len_array2) and float('inf') or nums2[array2_portion]

 if maxLeft_array1 <= minRight_array2 and maxLeft_array2 <= minRight_array1:
 if (len_array1 + len_array2) % 2 == 0:
                    median = (max(maxLeft_array2, maxLeft_array1) + min(minRight_array2, minRight_array1)) / 2
 return median
 else:
                    median = max(maxLeft_array1, maxLeft_array2)
 return median
 elif maxLeft_array1 > minRight_array2:
                high = array1_portion - 1
 else:
                low = array1_portion + 1