二分 - 尋找兩個有序陣列的中位數 - Leetcode 4

二分 - 尋找兩個有序陣列的中位數 - Leetcode 4

給定兩個大小分別為 m 和 n 的正序（從小到大）陣列 A 和 B，請你找出并回傳這兩個正序陣列的 中位數 ，

示例 1：

輸入：A = [1,3], B = [2]
輸出：2.00000
解釋：合并陣列 = [1,2,3] ，中位數 2

示例 2：

輸入：A = [1,2], B = [3,4]
輸出：2.50000
解釋：合并陣列 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

示例 3：

輸入：A = [], B = [1]
輸出：1.00000

示例 4：

輸入：A = [2], B = []
輸出：2.00000

方法一：劃分陣列（ O ( log ? 2 ( m i n ( n , m ) ) ) O(\log_2(min(n,m))) O(log2?(min(n,m)))）

我們可以把兩個陣列看成是一個陣列的兩段，然后設法在 A 或者 B 中找出中位數所在的位置，

這個做法需要理解中位數的作用：它把一個陣列劃分成了等長的兩段，

所以，我們首先設法把兩個陣列重新劃分成等長的兩段，假設是 left 段 和 right 段，使得 left 段的最大值不超過 right 段的最小值：

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

即：

• l e n ( l e f t ) = i + j = l e n ( r i g h t ) = n + m ? i ? j + [ n + m 是 奇 數 ] len(left)=i+j=len(right)=n+m-i-j+[n+m\ 是奇數] len(left)=i+j=len(right)=n+m?i?j+[n+m 是奇數]
• max ? ( l e f t ) ≤ min ? ( r i g h t ) \max(left)\le \min(right) max(left)≤min(right)

那么答案為：

n + m 為 偶 數 ： A n s = max ? ( l e f t ) + min ? ( r i g h t ) 2 n+m為偶數：Ans=\cfrac{\max(left)+\min(right)}{2} n+m為偶數：Ans=2max(left)+min(right)?

n + m 為 奇 數 ： A n s = max ? ( l e f t ) — — （ 左 邊 多 一 個 元 素 ） n+m為奇數：Ans=\max(left)\ ——（左邊多一個元素） n+m為奇數：Ans=max(left) ——（左邊多一個元素）

具體實作細節如下：

• 我們首先要在陣列 A 中二分出劃分的位置 i i i，滿足： max ? ( l e f t ) ≤ min ? ( r i g h t ) \max(left)\le \min(right) max(left)≤min(right)，即：
  max ? ( A [ i ? 1 ] , B [ j ? 1 ] ) ≤ min ? ( A [ i ] , B [ j ] ) \max(A[i-1],B[j-1])\le \min(A[i],B[j]) max(A[i?1],B[j?1])≤min(A[i],B[j])
  等價于： B [ j ? 1 ] ≤ A [ i ] & & A [ i ? 1 ] ≤ B [ j ] B[j-1]\le A[i] \ \ \&\&\ \ A[i-1]\le B[j] B[j?1]≤A[i] && A[i?1]≤B[j]
  我們仔細思考發現，上述條件是滿足”單調性的“，因為，我們多分給 left 一個元素，就少分給right 一個元素，即， i i i 遞增時， j j j 相應地遞減，也就是 A [ i ] A[i] A[i] 遞增， B [ j ] B[j] B[j] 就遞減，那么可以得出結論： A [ i ] A[i] A[i] 越大越好，越容易滿足約束條件，
  所以，我們可以二分出最大的，滿足條件的 A [ i ] A[i] A[i]，
• 注意，根據等長的條件，得到： j = ? m + n + 1 2 ? ? i j=\lfloor{\cfrac{m+n+1}{2}}\rfloor-i j=?2m+n+1???i，為了保證 j ≥ 0 j\ge 0 j≥0，簡化邊界的判斷，我們可以假設 m ≤ n m\le n m≤n，即 A 的長度 ≤ B 的長度，
• 然后我們維護出 max ? ( l e f t ) \max(left) max(left) 和 min ? ( r i g h t ) \min(right) min(right)，
• 最后根據奇偶性輸出答案即可，

代碼：

class Solution {
public:
     double findMedianSortedArrays(vector<int>& A, vector<int>& B) 
     {
        int m = A.size(), n = B.size();
        if(m > n) swap(A, B), swap(m, n);
        
        int l = 0, r = m;
        int max_left = 0, min_right = 0;
        int A_i, A_im1, B_j, B_jm1;
        int i, j;
        
        while(l < r)
        {
            i = l + r + 1 >> 1;
            j = (n + m + 1 >> 1) - i;
            
            // 事實上這里 i > 0 是必然成立的，相對的，j < n 也是必然成立的，
            if(A[i - 1] <= B[j]) l = i;
            else r = i - 1;
        }
        
        j = (n + m + 1 >> 1) - l;
        A_i = (l == m ? INT_MAX : A[l]);
        A_im1 = (l == 0 ? INT_MIN : A[l - 1]);
        B_j = (j == n ? INT_MAX : B[j]);
        B_jm1 = (j == 0 ? INT_MIN : B[j - 1]);
        
        max_left = max(A_im1, B_jm1);
        min_right = min(A_i, B_j);
        
        return (n + m & 1) ? max_left : (double)(max_left + min_right) / 2.0;
    }
};