[較難]LeetCode-4.尋找兩個正序數組的中位數 利用數組擴充和二分法切割思想實作

當我看到題目時，首先想到最簡單粗暴的方法是合并數組然後進行排序，但是這樣最快也隻能達到O(m+n)的級别，不符合題目要求。參考大神的題解後，寫一些我的感想。

首先利用數組擴充的思想，将兩個數組的和變成偶數，這樣友善統一處理。例如，傳入的數組為：

nums1:[5,9,10]
nums2:[2,6]
           

這樣兩個數組的和是奇數個，我們排好序試試：2,5,6,9,10

這樣我們一眼就可以看出來中位數是6，但是對于偶數個的數組計算方法又不一樣了。是以，可以把兩個數組都變成奇數個，相加後就是偶數個，然後再去求中位數：

#2#5#6#9#10#           

想象一下如果數組間存在這些#号，那麼不管什麼數組一定是奇數個。

在此基礎上，我們利用二分法對傳入的兩個數組進行切割

對nums1來說，在切割時切到了9，是以可以看成：5, 9/9 ,10

對nums2來說，在切割時剛好把兩個數分開：2 / 6

做出定義：

LMax1為nums1左側的最大元素，RMin1為nums1右側的最小元素

LMax2為nums2左側的最大元素，RMin2為nums2右側的最小元素

可以得知目前 LMax1=9 , RMin1=9 , LMax2=2, RMin2 = 6

LMax1≤RMin1 , LMax2≤RMin2 必定成立（題目說明是從小到大排序）

隻要滿足LMax1≤RMin2， LMax2≤RMin1，我們就可以使用下列公式獲得中位數

max(LMax1, LMax2) + min(RMin1, RMin2)) / 2
           

接下來看看代碼

#include <iostream>
#include <vector>
using namespace std;

/**
 * LeetCode
 * 4. 尋找兩個正序數組的中位數
 * https://leetcode-cn.com/u/banana798/
 */

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();

        if (n > m)  //保證數組1一定最短,這樣二分效率最高
        {
            return findMedianSortedArrays(nums2, nums1);
        }

        // Ci 為第i個數組的割,比如C1為2時表示第1個數組隻有2個元素。LMaxi為第i個數組割後的左元素。RMini為第i個數組割後的右元素。
        int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我們目前是虛拟加了'#'是以數組1是2*n長度

        while (lo <= hi)   //二分
        {
            c1 = (lo + hi) / 2;  //c1是二分的結果
            //這裡C2怎麼推導呢，我們可以知道改良後的數組有2m+1+2n+1=2m+2n+2個元素，為偶數個
            //兩個基數數組進行切割時會把一個元素切割開，變成2個（切2個變4個，相當于多了2個），是以切割後總數其實是2m+2n+4
            //切割後左邊元素整體為c1+1+c2+1
            //則有2m+2n+4-(c1+1+c2+1) = c1+1+c2+1 可推出c2
            c2 = m + n - c1;

            LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
            RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
            LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
            RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];

            if (LMax1 > RMin2)
                hi = c1 - 1;
            else if (LMax2 > RMin1)
                lo = c1 + 1;
            else
                break;
        }
        return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
    }
};


int main()
{
    // [#5#9#10#]
    vector<int> nums1 = {5,9,10};
    // [#2#6#]
    vector<int> nums2 = {2,6};

    Solution solution;
    cout << solution.findMedianSortedArrays(nums1, nums2);
    return 0;
}           

這個方案的難點：

1. 要清楚數組個數轉換為偶數個後如何映射到原數組（即映射關系）
2. 代碼中我詳細寫了c2變量的推導過程，這個一開始我也沒了解

總的來說，這個題很值得我們去研究，如果題目沒有要求時間複雜度的話我也不知道還有這種算法。