【算法】LeetCode 4 - Median of Two Sorted Arrays

2019.10.20

文章目錄

• • 思路
  • 原理
  • 代碼

思路

首先，擴充到一般情況有助于求解此題，假設我們要求解的是兩個有序序列的第k個元素。

然後，對于

log(m+n)

時間複雜度的要求，不難想到，采用二分法的思想，可以達到O(logn)級複雜度。具體推導此處略。

A[0, 1, ..., i, ..., m)  B[0, 1, ..., j, ..., n)
C[0, 1, ..., k-1, ..., m+n)
           

兩個數組A、B是有序序列，假設AB歸并排序後變成有序數組C，那麼一定存在

i∈[0,m), j∈[0,n)

，使得

A[0, i]∪B[0, j]

集合的個數為k個，且

A[i] <= B[j+1] && B[j] <= A[i+1]

，即

A[0, i]∪B[0, j]

的k個元素是C中最小的k個元素，那麼C的第k個元素

C[k-1] = max{A[i], B[j]}

。

原理

原理大概總結如下：如思路中所說，我們的目标是找到符合條件的i, j，但

A[i] <= B[j+1] && B[j] <= A[i+1]

不容易滿足；一旦不滿足，我們可采用二分法思想縮小查找範圍，直到找到為止。具體說明如下：

left           right
A[0, i]  |  A[i+1, m)
B[0, j]  |  B[j+1, n)
           

為了簡化求解，我們令

i = j

，即

i = j = k / 2 - 1

（注意k的最小值是1）；且m <= n。

1. A[i] <= B[j+1] && B[j] <= A[i+1]

   ，即

   max{left} <= min{right}

   ，此時第k個元素為：

C[k] = max{A[i], A[j]} （k為偶數）
     = min{A[i+1], A[j+1]}（k為奇數）
           

1. 若

   A[i+1] < B[j]

   ，即

   A[i] <= B[j]

   ，可排除

   A[0, i]

   ，因為第k個元素一定不在

   A[0, i]

   中：

反證法：
假設第k個元素在A[0, i]中，即C[k-1] = A[i']，0<= i' <= i
那麼，就必須在B數組中找到 k - i' 個元素，即 k / 2 + 1 個元素
使得，B[j']（0<= j' < k-i'）都小于A[i']
然而，A[i] <= B[j]，B中最多隻有j個元素，即 k / 2 - 1 個元素可能小于A[i']
沖突
是以，第k個元素一定不在B[0, j]中
           

1. 若

   B[j+1] < A[i]

   ，即

   B[j] <= A[i]

   ，同理可證，第k個元素一定不在

   B[0, j]

   中。
2. 我們再讨論一下邊界條件，上面成立的條件是

   0 <= k/2 - 1 < m <= n

   ：

   4.1

   k/2 - 1 < 0

   ，即

   k<2 -> k = 1

   時，顯然第k個元素為

   min{A[0], B[0]}

   ；

   4.2

   k/2 - 1 >= m

   ，即

   A[0, m)

   無法繼續被拆分成兩個部分，那麼可排除

   B[0, j]

   ：

反證法：
假設第k個元素在B[0, j]中，即C[k-1] = A[j']，0<= j' <= j
那麼，就必須在A數組中找到 k - j' 個元素，即 k / 2 + 1 個元素
使得，A[i']（0<= i' < k-j'）都小于B[j']
然而，m <= k/2 - 1
沖突
是以，第k個元素一定不在B[0, j]中
           

代碼

public double func(int[] foo, int[] bar) {
    int size = foo.length + bar.length;
    return ( iter(foo, 0, bar, 0, (size + 1)/2),
             iter(foo, 0, bar, 0, (size + 2)/2) )/(double)2;
}
public static int iter(int[] foo, int s1, int[] bar, int s2) {
    if (s1 >= foo.length) return bar[s2 + k - 1];
    if (s2 >= bar.length) return foo[s1 + k - 1];
    if (k == 1) return Math.min(foo[s1], bar[s2]);
    
    int step = k/2;
    int i = s1 + step - 1;
    int j = s2 + step - 1;
    int fooMid = i < foo.length ? foo[i] : Integer.MAX_VALUE;
    int barMid = j < bar.length ? bar[j] : Integer.MAX_VALUE;
    if (fooMid < barMid) {
        return iter(foo, s1 + step, bar, s2, k - step);
    } else {
        return iter(foo, s1, bar, s2 + step, k - step);
    }
}