算法連載之求解兩個有序數組的中位數

問題

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。找出這兩個有序數組的中位數。假設 nums1 和 nums2 不會同時為空。

示例 1:

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.

合併兩個有序數組來獲得中位數

1、先將兩個有序數組合併為一個有序數組

2、再獲取中位數

偶數情況中位數索引分別為：(m+n)/2-1，(m+n)/2。將二值求平均數。

計數情況中為數索引為：(m+n)/2

時間複雜度是O(m+n)，空間複雜度是O(m+n)。

優化第一個求解方法

上一個算法是將兩個有序數組合併為一個有序數組再計算中位數位置。我們可以先計算中位數位置，將兩個有序數組元素逐一比較排序過程中，當索引位置到達中位數時停止。

時間複雜度是O((m+n)/2+1)=O(m+n)，空間複雜度是((m+n)/2+1)=O(m+n)。

二分查找

• 一個有序數組的中位數

長度為偶數：

數組a，索引位置初始為0，長度為m。索引 i 將有序數組劃分為左右兩個長度相等的部分，i = (m - 0) / 2 且必須滿足如下兩個條件：

1、length(a[0, i)) = length(a[i, m))

2、a[i-1] <= a[i]

則中位數是 (a[i-1] + a[i]) / 2

長度為基數：

數組a，索引位置初始為0，長度為m。索引 i 將有序數組劃分為左右兩個部分，其中左邊部分比右邊部分少一個元素，i = (m - 0) / 2 且必須滿足如下兩個條件：

1、length(a[0, i)) + 1 = length(a[i, m))

2、a[i-1] <= a[i]

則中位數是 a[i]

• 兩個有序數組的中位數

兩個有序數組長度之和為偶數：

兩個a和b有序數組的長度分別是m和n。對a數組的一個劃分i和對b數組的一個劃分j，使得a數組的左半部分同b數組的左半部分看作合併後有序數組c的左半部分；而a數組的右半部分同b數組的右半部分看作合併後有序數組c的右半部分。假設有i、j存在，則需滿足如下條件：

1、length(a[0, i)) + length(b[0, j]) = length(a[i, m)) + length(b[j, n])

(i-0)+(j-0)=(m-i)+(n-j)

i=(m+n)/2-j

2、max(a[i-1], b[j-1]) <= min(a[i], b[j])

則中位數是 (max(a[i-1], b[j-1]) + min(a[i], b[j])) / 2

兩個有序數組長度之和為基數：

兩個a和b有序數組的長度分別是m和n。對a數組的一個劃分i和對b數組的一個劃分j，使得a數組的左半部分同b數組的左半部分看作合併後有序數組c的左半部分；而a數組的右半部分同b數組的右半部分看作合併後有序數組c的右半部分。假設有i、j存在，則需滿足如下條件：

1、length(a[0, i)) + length(b[0, j]) + 1 = length(a[i, m)) + length(b[j, n])

(i-0)+(j-0)+1=(m-i)+(n-j)

i=(m+n-1)/2-j

2、max(a[i-1], b[j-1]) <= min(a[i], b[j])

則中位數是 min(a[i], b[j])

分析求解：

兩個有序數組長度不管是基數還是偶數，都需要滿足如上兩個條件。其中第二個條件相同，而第一個條件我們可以歸納簡化為i=(m+n)/2-j，因為當m+n為基數時 (m+n)/2-j = (m+n-1)/2-j。所以，只要找出數組a劃分i，則可以通過公式i=(m+n)/2-j，得到數組b劃分j，並且滿足如下兩個條件：

1、i=(m+n)/2-j

2、max(a[i-1], b[j-1]) <= min(a[i], b[j])

我們可以在數組a中，通過折半查找來取得劃分i。其中IMIN為開始索引0，IMAX為數組a長度m

1）將數組a折半 i = (IMAX - IMIN) / 2

2）其中a[i-1]<=a[i]，b[j-1]<=b[j]一定是成立的。

若b[j-1]>a[i]不符合條件，i只有向後移動一位變大，相應的j向前移動一位變小，才有可能符合條件b[j-1]<=a[i]。所以，此時的i並不是有效劃分，有效劃分在i+1~IMAX範圍內。IMIN賦值為i+1，繼續執行1）。

若a[i-1]>b[j]不符合條件，i只有向前移動一位變小，相應的j向後移動一位變大，才有可能符合條件a[i-1]<=b[j]。所以，此時的i並不是有效劃分，有效劃分在IMIN~i-1範圍內。IMAX為i-1，繼續執行1）。

3）最後找到合適的i和j，就可以直接計算得到中位數。

注意：

1、數組a和數組b長度的關係

必須保證0<=i<=m, 0<=j<=n；假設0<=i<=m成立，如果滿足0<=j<=n，m和n之間的關係。

1）

i=(m+n)/2-j =>

j=(m+n)/2-i =>

因為i<=m，所以j=(m+n)/2-i>=(m+n)/2-m=(n-m)/2 =>

若(n-m)/2>=0，則j>=0 =>

m<=n

2）

i=(m+n)/2-j =>

j=(m+n)/2-i =>

因為i>=0，j=(m+n)/2-i<=(m+n)/2 =>

若(m+n)/2<=n，則j<=n =>

m<=n

3）

總結：當m<=n時，0<=i<=m，可以保證0<=j<=n。所以，在算法中，始終要保持數組a的長度要不大於數組b的長度。

數組a可能為空數組

2、i，j移動過程中的越界問題

1）若b[j-1]>a[i]不符合條件，i只有向後移動一位變大，相應的j向前移動一位變小，才有可能符合條件b[j-1]<=a[i]。

為保證數組不越界，j不能等於0，i不能等於m。

這兩種情況要單獨判斷：

當j==0時，左半部分的最大值是a[i-1]，右半部分的最小值是min(a[i], b[0])；

當i==m時，左半部分的最大值是max(a[m-1], b[j-1])，右半部分的最小值是b[j]。

2）若a[i-1]>b[j]不符合條件，i只有向前移動一位變小，相應的j向後移動一位變大，才有可能符合條件a[i-1]<=b[j]。所以，此時的i並不是有效劃分，有效劃分在0~i範圍內。IMIN賦值為0，IMAX為i，繼續執行1）。

為保證數組不越界，i不能等於0，j不能等於n。

這兩種情況要單獨判斷：

當i==0時，左半部分的最大值是b[j-1]，右半部分的最小值是min(a[0], b[j])；

當j==n時，左半部分的最大值是max(a[i-1], b[n-1])，右半部分的最小值是a[i]。

時間複雜度是O(log(min(m,n)))，空間複雜度是O(1)。

性能分析

隨機生成兩個有序數組進行性能測試：

The Median is 512203030.5 by MergedSortedArrays solve(num1.length=42385384,num2.length=19210176), using time is 349 milliseconds.

The Median is 512203030.5 by OptimizingMergedSortedArrays solve(num1.length=42385384,num2.length=19210176), using time is 195 milliseconds.

The Median is 512203030.5 by Binary solve(num1.length=42385384,num2.length=19210176), using time is 0 milliseconds.

二分查找法性能最優，符合預期。