本文共 2233 字，大约阅读时间需要 7 分钟。

有两个大小为 m 和 n 的排序数组 nums1 和 nums2 。

请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。

示例 1:

nums1 = [1, 3]nums2 = [2]中位数是 2.0

示例 2:

nums1 = [1, 2]nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5

这个讲得很好了。

思路：对长度较短的数组进行二分查找，时间复杂度为O(log(min(m,n))).

假设A为较短数组（如果A为较长数组，先对两个数组进行swap），长度为m，B为较长数组，长度为n。

将A、B分别划分成左右两部分：

对于A，划分点的位置可以有m+1种选择；对于B，划分点的位置可以有n+1种选择。

只需要保证：

（1）A[i-1]<=B[j] && B[j-1]<=A[i]

（2）i+j=m-i+n-j （m+n为偶数），或者i+j=m-i+n-j+1（m+n为奇数）即可。即j=(n+m+1)/2-i 

因此当m+n为偶数时，中位数为(max(A[i-1], B[j-1])+min(A[i], B[j]))/2，当m+n为奇数时，中位数为max(A[i-1], B[j-1])。

二分过程中，若A[i-1]>B[j]，则i左移动，继续查找。若B[j-1]>A[i]，则i右移动，继续查找。

着重介绍一下怎么处理边界：

1、需要满足条件：B[j-1] <= A[i] and A[i-1] <= B[j]

2、某些边界情况下，i=0/i=m/j=0/j=n，有些不存在了。这个时候只需要满足存在的即可。

3、所以需要满足条件： (j == 0 or i == m or B[j-1] <= A[i]) and (i == 0 or j == n or A[i-1] <= B[j])

两两组合一共九种情况，排除掉一些不可能的情况，这个时候只剩下5小类：

（1）i == 0 && B[j-1]<=A[i]

（2）j == n && B[j-1]<=A[i] 

（3）i == m && A[i-1]<=B[j] 

（4）j == 0 && A[i-1]<=B[j]

（5）B[j-1] <= A[i] and A[i-1] <= B[j]

再对5类进行逐步分析，只剩下8种情况，11诚不欺我！具体如下图：

class Solution {public:    double findMedianSortedArrays(vector
   
    & A, vector
    
     & B) {        int m = min(A.size(), B.size()), n = max(A.size(), B.size()), i, j, l = 0, r = m;        if (A.size() > B.size()){            swap(A, B);        }        if (A.empty()) return n % 2 == 0 ? (B[n / 2 - 1] + B[n / 2]) / 2.0 : B[n / 2];        while (l <= r)        {            i = (l + r) / 2;            j = (m + n + 1) / 2 - i;            if (i != 0 && j != n && A[i - 1] > B[j]){                r = i - 1;            }            else if (j != 0 && i != m && B[j - 1] > A[i]){                l = i+1;            }            else{ //找到i                if (i == 0 && B[j - 1] <= A[i]){                    if(m==n) return (A[i]+B[j-1])/2.0;                    else return (m+n)%2==0 ? (B[j-1]+min(A[i], B[j]))/2.0 :B[j-1];                }                if (i ==m && A[i - 1] <= B[j]){                    if(m==n) return (A[i-1]+B[j])/2.0;                    else return (m+n)%2==0 ? (max(B[j-1],A[i-1]) + B[j])/2.0 :max(A[i-1], B[j-1]);                }                else{                    return (m+n)%2==0 ? (max(A[i-1], B[j-1])+min(A[i], B[j]))/2.0 : max(A[i-1], B[j-1]) ;                }            }        }          return 0;    }};
    
   

转载地址：http://whabi.baihongyu.com/