摘要：題目解答方法一由于兩個(gè)數(shù)組都是排好序的，因此首先可以想到的思路就是利用歸并排序把兩個(gè)數(shù)組合并成一個(gè)有序的長數(shù)組，然后直接取出中位數(shù)即可。如果滿足條件，則直接返回求取中位數(shù)。如果減小，則增加，左邊序列數(shù)組的值會(huì)更小，右邊序列數(shù)組的值會(huì)更大。

2.1. 方法一

由于兩個(gè)數(shù)組都是排好序的，因此首先可以想到的思路就是利用歸并排序把兩個(gè)數(shù)組合并成一個(gè)有序的長數(shù)組，然后直接取出中位數(shù)即可。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        len1 = len(nums1)
        len2 = len(nums2)
        nums = []
        
        i = 0
        j = 0
        
        while (i < len1 and j < len2):
            
            if (nums1[i] <= nums2[j]):
                nums.append(nums1[i])
                i += 1
            
            else:
                nums.append(nums2[j])
                j += 1
        
        if (i < len1):
            while(i < len1):
                nums.append(nums1[i])
                i += 1
            
        if (j < len2):
            while(j < len2):
                nums.append(nums2[j])
                j += 1
        
        odd = (len1 + len2) % 2 # 長度是否為奇數(shù)
        mid = (len1 + len2 - 1) // 2
        if (odd):
            return nums[mid]
        else:
            return (nums[mid] + nums[mid+1]) / 2

因?yàn)橐闅v兩個(gè)數(shù)組，所以時(shí)間復(fù)雜度為 $O(m+n)$，而題目中要求算法的時(shí)間復(fù)雜度為 $O(log (m+n))$，因此應(yīng)該是有更高效的算法，借助于二分查找。

2.2. 方法二

所謂中位數(shù)，就是將 K 個(gè)數(shù)據(jù)分為長度相等的兩組，左邊的數(shù)據(jù)小于等于右邊的數(shù)據(jù)。

如果我們要在任意位置 $i$ 處將長度為 $m$ 的數(shù)組 $A$ 分為兩部分，則共有 $m+1$ 種分法，$i=[0, m]$。

$$ left\_part quad | quad right\_part$$
$$ A[0], A[1], ..., A[i-1] quad | quad A[i], A[i+1], ..., A[m-1]$$

$i=0$ 說明左半部分沒有元素，反之 $i=m$ 說明右半部分沒有元素。左半邊元素個(gè)數(shù)為 $i$ ，右半邊元素個(gè)數(shù)為$m-i$。

同理，我們可以在任意位置 $j$ 處將長度為 $n$ 的數(shù)組 $B$ 分為兩部分，則共有 $n+1$ 種分法，$j=[0, n]$。

$$ B[0], B[1], ..., B[j-1] quad | quad B[j], B[j+1], ..., B[n-1]$$

針對劃分完后的數(shù)組 $A$ 和 $B$，如果滿足：

左邊部分的長度等于右邊部分的長度（偶數(shù)情況），$i+j = m-i + n-j$；或者等于右邊部分的長度加 1（奇數(shù)情況） ,$i+j = m-i + n-j+1$。

左邊的最大元素小于等于右邊的最小元素，$A[i-1] <= B[j] quad and quad B[i-1] <= A[j]$。

那我們也就找到了中位數(shù)，$median = frac{max(left\_part) + min(right\_part)}{2}$。

所以，我們要做的就是在 $i=[0, m]$ 區(qū)間搜索一個(gè) $i$ 值，使得上面的條件得到滿足。也即

$$ A[i-1] <= B[j] quad and quad B[i-1] <= A[j] ，其中 quad j = frac{m+n+[1]}{2}-i$$

加不加 1 取決于總的長度是奇數(shù)還是偶數(shù)，同時(shí)，為了保證 $j$ 的范圍在 $[0, n]$，我們必須要求 $n <= m$。

接下來，我們就在 $i=[0, m]$ 區(qū)間進(jìn)行二分查找。

如果滿足條件，則直接返回求取中位數(shù)。

如果 $i > 0 quad and quad A[i-1] > B[j]$，則減小 $i$。如果增加 $i$，則 $j$ 減小，左邊序列數(shù)組 $A$ 的值會(huì)更大，右邊序列數(shù)組 $B$ 的值會(huì)更小。

如果 $i < m quad and quad B[i-1] > A[j]$，則增加 $i$。如果減小 $i$，則 $j$ 增加，左邊序列數(shù)組 $A$ 的值會(huì)更小，右邊序列數(shù)組 $B$ 的值會(huì)更大。

最后，我們求得左半部分的最大值以及右半部分的最小值，然后就可以求出中位數(shù)了。

因?yàn)椋檎业姆秶鸀?$i=[0, m]$，而且每次查找縮小區(qū)間為原來的一半，因此時(shí)間復(fù)雜度為 $O(log(min(m, n))$，空間復(fù)雜度為 $O(1)$。

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        
        
        int m = nums1.size();
        int n = nums2.size();
        int len = m + n;
        int odd = len % 2;
        
        int left = 0;
        int i = 0, j = 0;  
        vector::iterator A = nums1.begin();
        vector::iterator B = nums2.begin();
        
        // 確保數(shù)組 A 的長度小于等于數(shù)組 B 的長度
        if (m > n)
        {
            int temp = m;
            m = n;
            n = temp;
            A = nums2.begin();
            B = nums1.begin();
        }
        
        int right = m;
                
        while(left <= right)
        {
            i = left + (right - left) / 2;
            j = (len + odd) / 2 - i;
                        
            if (i > 0 && A[i-1] > B[j])
            {
                right = i - 1;
            }
            else if(i < m && B[j-1] > A[i])
            {
                left = i + 1;
            }
            else
            {
                break;
            } 
        }
         
        int left_max = 0;
        int right_min = 0;
        
        // 左半部分的最大值
        if (i == 0) left_max = B[j-1];
        else if (j == 0) left_max = A[i-1];
        else  left_max = A[i-1] <= B[j-1] ? B[j-1] : A[i-1];

        // 右半部分的最小值
        if (i == m) right_min = B[j];
        else if (j == n) right_min = A[i];
        else    right_min = A[i] <= B[j] ? A[i] : B[j];

        if (odd)
        {
            return left_max;
        }
        else
        {
            return float(left_max + right_min) / 2;
        }
    }
};

獲取更多精彩，請關(guān)注「seniusen」!