初中有個(gè)老師說(shuō)過(guò)，能解決問(wèn)題的人不一定是最牛逼的，最牛逼的人是能夠避免這些問(wèn)題的人。
不愧是困難難度的題，emmm~看答案都有點(diǎn)困難，跟zz梁一起看了印度老哥講解的視頻才明白是什么思路。
然后就開始自己寫，首先進(jìn)行了一下判定，如果第一個(gè)數(shù)組比第二個(gè)長(zhǎng)，就調(diào)取自身，把兩個(gè)字符串調(diào)換位置作為輸入，一下子解決了一半的問(wèn)題，開心。然而這只是噩夢(mèng)的開始。在找中位數(shù)的過(guò)程中，要判斷邊界條件，否則很容易用到數(shù)組外的下標(biāo)，造成報(bào)錯(cuò)。另外，數(shù)組的奇偶也會(huì)影響邊界的判斷。然后我寫了幾十行，基本上都是在判斷邊界條件，然后一運(yùn)行就錯(cuò)。然后我就直接看了別人得答案，很直觀。我粘一下。

作者：bian-bian-xiong
鏈接：https://leetcode-cn.com/problems/two-sum/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

算法:
為了解決這個(gè)問(wèn)題，我們需要理解 “中位數(shù)的作用是什么”。在統(tǒng)計(jì)中，中位數(shù)被用來(lái)：
將一個(gè)集合劃分為兩個(gè)長(zhǎng)度相等的子集，其中一個(gè)子集中的元素總是大于另一個(gè)子集中的元素。
這其中又分為偶數(shù)組和奇數(shù)組：
奇數(shù)組:[2 3 5] 對(duì)應(yīng)的中位數(shù)為3
偶數(shù)組: [1 4 7 9] 對(duì)應(yīng)的中位數(shù)為(4 + 7) /2 = 5.5
先解釋下“割”
我們通過(guò)切一刀，能夠把有序數(shù)組分成左右兩個(gè)部分，切的那一刀就被稱為割(Cut)，割(Cut)的左右會(huì)有兩個(gè)元素，分別是左邊最大值和右邊最小值。
我們定義LMax= Max(LeftPart)，RMin = Min(RightPart)。
割可以割在兩個(gè)數(shù)中間，也可以割在1個(gè)數(shù)上，如果割在一個(gè)數(shù)上，那么這個(gè)數(shù)即屬于左邊，也屬于右邊
奇數(shù)組:[2 3 5] 對(duì)應(yīng)的中位數(shù)為3，假定割(Cut)在3上，我們可以把3分為2個(gè)：[2 （3/3) 5]
因此LMax=3, RMin=3
偶數(shù)組: [1 4 7 9] 對(duì)應(yīng)的中位數(shù)為(4 + 7) /2 = 5.5,假定割(Cut)在4和7之間：[1 （4/7) 9]
因此LMax=4, RMin=7
割和第k個(gè)元素
一個(gè)數(shù)組
對(duì)于一個(gè)有序數(shù)組，對(duì)于數(shù)組A,如果在k的位置割(Cut)一下（不是割(Cut)在兩數(shù)中間），那么LMax = RMin = A[k],
兩個(gè)數(shù)組
也就是我們題目的狀態(tài)，我們要求得兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組時(shí)，第k位的元素
我們?cè)O(shè):
Ci為第i個(gè)數(shù)組的割。
LMaxi為第i個(gè)數(shù)組割后的左元素.
RMini為第i個(gè)數(shù)組割后的右元素。

首先，LMax1<=RMin1，LMax2<=RMin2 這是肯定的，因?yàn)閿?shù)組是有序的，左邊肯定小于右邊!，而如果割(Cut)在某個(gè)數(shù)上，則左右相等。
其次，如果我們讓LMax1<=RMin2，LMax2<=RMin1 呢

那么如果左半邊全小于右半邊，如果左邊的元素個(gè)數(shù)相加剛好等于k, 那么第k個(gè)元素就是Max(LMax1, LMax2)，這個(gè)比較好理解的，因?yàn)镸ax(LMax1, LMax2)肯定是左邊k個(gè)元素的最大值，因?yàn)楹喜⒑蟮臄?shù)組是有序，第k個(gè)元素肯定前面k個(gè)元素中最大的那個(gè)。
那么如果 LMax1>RMin2，說(shuō)明數(shù)組1的左邊元素太大（多），我們把C1減小，C2=k-C1也就相應(yīng)的增大。LMax2>RMin1同理，把C2減小，C1=k-C2也就相應(yīng)的增大。
假設(shè)k=3
對(duì)于
[2 3 5]

[1 4 7 9]

設(shè)C1 = 1, 那么C2 = k - C1 = 2
[2 / 3 5]
[1 4 / 7 9]
這時(shí)LMax1 =2, RMin1 = 3, LMax2=4, RMin2=7,
從而有LMax2 > RMin1,依據(jù)前面的推論，我們要將C1增大，所以我們讓C1 = 2，如下：
[2 3 /5]
[1 / 4 7 9]
這時(shí)LMax1 =3, RMin1 = 5, LMax2=1, RMin2=4, 滿足 LMax1 < RMin2 且 LMax2 < RMin1, 所以第3個(gè)元素為Max(LMax1,LMax2) = 3
兩個(gè)數(shù)組的最大問(wèn)題是，它們合并后，m+n總數(shù)可能為奇, 也可能為偶，所以我們得想法讓m+n總是為偶數(shù)
通過(guò)虛擬加入‘#’，我們讓m轉(zhuǎn)換成2m+1 ，n轉(zhuǎn)換成2n+1, 兩數(shù)之和就變成了2m+2n+2，恒為偶數(shù)。
注意是虛擬加，其實(shí)根本沒(méi)這一步，通過(guò)下面的轉(zhuǎn)換，我們可以保證虛擬加后每個(gè)元素跟原來(lái)的元素一一對(duì)應(yīng)

這么虛擬加后，每個(gè)位置可以通過(guò)/2得到原來(lái)元素的位置：
比如 2，原來(lái)在0位，現(xiàn)在是1位，1/2=0
比如 3，原來(lái)在1位，現(xiàn)在是3位，3/2=1
比如 5，原來(lái)在2位，現(xiàn)在是5位，5/2=2
比如 9，原來(lái)在3位，現(xiàn)在是7位，7/2=3
而對(duì)于割(Cut)，如果割在‘#’上等于割在2個(gè)元素之間，割在數(shù)字上等于把數(shù)字劃到2個(gè)部分，總是有以下成立：
LMaxi = (Ci-1)/2 位置上的元素
RMini = Ci/2 位置上的元素

例如：
割在3上，C = 3，LMax=a[(3-1)/2]=A[1]，RMin=a[3/2] =A[1]，剛好都是3的位置！
割在4/7之間‘#’，C = 4，LMax=A[(4-1)/2]=A[1]=4 ，RMin=A[4/2]=A[2]=7
剩下的事情就好辦了，把2個(gè)數(shù)組看做一個(gè)虛擬的數(shù)組A，A有2m+2n+2個(gè)元素，割在m+n+1處，所以我們只需找到m+n+1位置的元素和m+n+2位置的元素就行了。
左邊：A[m+n+1] = Max(LMax1,LMax2)
右邊：A[m+n+2] = Min(RMin1,RMin2)
==>Mid = (A[m+n+1]+A[m+n+2])/2 = (Max(LMax1,LMax2) + Min(RMin1,RMin2) )/2
最快的割(Cut)是使用二分法，
有2個(gè)數(shù)組，我們對(duì)哪個(gè)做二分呢？
根據(jù)之前的分析，我們知道了，只要C1或C2確定，另外一個(gè)也就確定了。這里，為了效率，我們肯定是選長(zhǎng)度較短的做二分，假設(shè)為C1。
LMax1>RMin2，把C1減小，C2增大?！?gt; C1向左二分
LMax2>RMin1，把C1增大，C2減小?！?gt; C1向右二分
如果C1或C2已經(jīng)到頭了怎么辦？
這種情況出現(xiàn)在：如果有個(gè)數(shù)組完全小于或大于中值。假定n<m, 可能有4種情況：
C1 = 0 —— 數(shù)組1整體都在右邊了，所以都比中值大，中值在數(shù)組2中，簡(jiǎn)單的說(shuō)就是數(shù)組1割后的左邊是空了，所以我們可以假定LMax1 = INT_MIN
C1 =2n —— 數(shù)組1整體都在左邊了，所以都比中值小，中值在數(shù)組2中 ，簡(jiǎn)單的說(shuō)就是數(shù)組1割后的右邊是空了，所以我們可以假定RMin1= INT_MAX，來(lái)保證LMax2<RMin1恒成立
C2 = 0—— 數(shù)組2整體在右邊了，所以都比中值大，中值在數(shù)組1中 ，簡(jiǎn)單的說(shuō)就是數(shù)組2割后的左邊是空了，所以我們可以假定LMax2 = INT_MIN
C2 = 2m—— 數(shù)組2整體在左邊了，所以都比中值小，中值在數(shù)組1中, 簡(jiǎn)單的說(shuō)就是數(shù)組2割后的右邊是空了，為了讓LMax1 < RMin2恒成立，我們可以假定RMin2 = INT_MAX

因?yàn)閺?fù)制過(guò)來(lái)格式有變化，所以建議去原鏈接處看。代碼如下：
可以說(shuō)非常牛逼了

#include <stdio.h>
#include <vector>
using namespace std;

#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)  //保證數(shù)組1一定最短
        {
            return findMedianSortedArrays(nums2, nums1);
        }

        // Ci 為第i個(gè)數(shù)組的割,比如C1為2時(shí)表示第1個(gè)數(shù)組只有2個(gè)元素。LMaxi為第i個(gè)數(shù)組割后的左元素。RMini為第i個(gè)數(shù)組割后的右元素。
        int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我們目前是虛擬加了'#'所以數(shù)組1是2*n長(zhǎng)度

        while (lo <= hi)   //二分
        {
            c1 = (lo + hi) / 2;  //c1是二分的結(jié)果
            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(int argc, char *argv[])
{
    vector<int> nums1 = { 2,3, 5 };
    vector<int> nums2 = { 1,4,7, 9 };
    Solution solution;
    double ret = solution.findMedianSortedArrays(nums1, nums2);
    return 0;
}

···