1 题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例1

1
2
3

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例2

1
2
3

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例3

1
2

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例4

1
2

输入：nums1 = [], nums2 = [1]
输出：1.00000

2 解题

2.1 二分查找

见二分查找

2.2 划分数组

为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：

1

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

如果理解了中位数的划分作用，我们就很接近答案了。

首先，让我们在任一位置i将 A 划分成两个部分：

1
2

left_A					|	right_A
A[0],A[1],...,A[i-1]	|	A[i],A[i+1],...,A[m-1]

其中A中有m个元素，则我们有m+1中划分的方法（$i=0 \to m$）

我们知道： $$ \begin{align} & len(leftA) = i,len(rightA) = m-i\\
& 注意：当i=0时，leftA为空集，当i=m时，right A为空集。 \end{align} $$ 采用同样的方式，我们在任一位置j将B划分为两个部分：

1
2

left_B					|	right_B
B[0],B[1],...,B[i-1]	|	B[i],B[i+1],...,B[m-1]

如果我们可以确认：

$$ \begin{align} & len(leftPart) = len(rightPart) \\
& \max(leftPart) \leq \min(rightPart)

\end{align} $$

那么，我们已经将 {A,B} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。那么：$median=\frac{\max(leftPart)+\min(rightPart)}{2}$

要保证这两个条件，我们只需要:

$$ \begin{align} &1.i+j=m-i+n-j \ (或：m-i+n-j+1) \\
&若n\geq m,只需要使用i=0 \to m,j=\frac{m+n+1}{2}-i \\
&2.B[j-1]\leq A[i]以及A[i-1]\leq B[j] \end{align} $$ ps.1 为了简化分析，我们$A[i-1],B[j-1],A[i],B[j]$总是存在，哪怕出现$i=0,i=m,j=0,j=n$这样的临界条件。最后再讨论如何处理这些临界值。 ps.2为什么$n\geq m$?由于$0\leq i \geq m$且$j = \frac {m+n+1}{2} - i$,保证j不是负数。如果$n<m$,那么j可能为负数，导致错误的结果。

所以，我们需要做的是， $$ \begin{align} & 在[0,m]中搜索并找到目标对象i，以使：\\
& B[j-1]\leq A[i]且A[i-1] \leq B[j] ,其中j=\frac{m+n+1}{2}-i \end{align} $$ 接着，我们可以按照以下步骤来进行二叉树搜索：

$$ \begin{align} &1.设i_{min}=0,i_{max}=m,然后开始在[i_{min},i_{max}]中进行搜索\\
&2.令i=\frac{i_{min}+i_{max}}{2},j=\frac{m+n+1}{2} - i \\
&3.现在我们有len(left_part)=len(right_part).而且只会遇到三种情况：\\
& \ \ * B[j-1] \leq A[i]且A[i-1]\leq B[j]: \\
& \ \ 这意味着我们找到了目标对象i，所以可以停止搜索。\\
& \ \ * B[j-1] > A[i] \\
& \ \ 这意味着A[i]太小，我们必须调整i以使B[j-1] \leq A[i] \\
& 我们可以增大i吗？\\
& —是的，因为i增加的时候，j会被减少。\\
& — 则B[j-1]会减小，而A[i]会增大，那么B[j-1] \leq A[i]就可能被满足。\\
& 我们可以减少i吗？\\
& —不能，因为i减少的时候，j会被增大。\\
& — 则B[j-1]会增大，而A[i]会减少，那么B[j-1] \leq A[i]就不会满足。\\
& 所以我们必须增大i。也就是说，必须将搜索范围调整为[i+1,i_{max}]。 因此，设i_{min} = i+1，并转到步骤 2\\
& \ \ * A[i-1] > B[j]:这意味着A[i-1]太大，我们必须减小i以使 A[i-1] \leq B[j]。 也就是说，我们必须将搜索范围调整为[i_{min},i-1]。\\
&因此，设 i_{max}=i-1 ，并转到步骤 2。 \end{align} $$

当找到目标对象i时，中位数为： $$ \begin{align} & 当m+n为奇数时，中位数=\max(A[i-1],B[j-1])\ & 当m+n为偶数时，中位数=\frac{\max(A[i-1],B[j-1])+\min(A[i],B[j])}{2} \end{align} $$

特殊情况：临界值 $i=0,i=m,j=0,j=n$,此时$A[i-1],B[j-1],A[i],B[j]$可能不存在。 其实这种情况比你想象的要容易得多。

我们需要做的是确保$\max(left_part) \leq \min(right_part)$。 因此，如果i和j不是临界值（这意味着 $A[i-1],B[j-1],A[i],B[j]$全部存在）, 那么我们必须同时检查 $A[i-1] \leq B[j]$ 以及 $B[j-1] \leq A[i]$ 是否成立。 但是如果$A[i-1],B[j-1],A[i],B[j]$中部分不存在，那么我们只需要检查这两个条件中的一个（或不需要检查）。 举个例子，如果 $i=0$，那么 $A[i-1]$ 不存在，我们就不需要检查 是否成立。 $A[i-1] \leq B[j]$所以，我们需要做的是： $$ \begin{align} & 在 [0,m] 中搜索并找到目标对象i，以使：\
& (j=0 \ or \ i=m \ or \ B[j-1] \leq A[i]) 或是\
& (i=0 \ or \ j=n \ or \ A[i-1] \leq B[j]) 其中j=\frac{m+n+1}{2}-i

\end{align} $$

1
2

注：i是从0开始找的，若找到i=m，就说明i是完美的
同理j也是一个道理

$$ \begin{align} & 1.(j=0 \ or \ i=m \ or \ B[j-1] \leq A[i]) 或是\
& (i=0 \ or \ j=n \ or \ A[i-1] \leq B[j]) 这说明i已经被找到，停止搜索 \
&2.j>0 \ and \ i<m \ and \ B[j-1] > A[i],这说明i小了，需要增大。\
&3.i>0 \ and \ j < n \ and \ A[i-1] > B[j]),这说明i大了，需要减小。

\end{align} $$

同时$i<m \Rightarrow j>0以及i>0 \Rightarrow j<n$始终成立，是因为： $$ \begin{align} & m \leq n, i<m \Rightarrow j=\frac{m+n+1}{2} - i \geq \frac{m+n+1}{2} - m \geq \frac{2m+1}{2} - m \geq 0\
& m \leq n, i>0 \Rightarrow j=\frac{m+n+1}{2} - i < \frac{m+n+1}{2} \leq \frac{2n+1}{2} \leq n \end{align} $$ 所以，在情况 2 和 3 中，我们不需要检查j>0 或是j<n 是否成立。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

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

    // 避免j为负，必须保证m<n
    // 若m>n,交换两容器的值，以及容器大小
    if (m > n) 
    {
        std::vector<int> temp;
        temp = nums1;
        nums1 = nums2;
        nums2 = temp;

        int tmp = m;
        m = n;
        n = tmp;
    }
    //区间[0,m]搜寻i
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        
    while (iMin <= iMax)
    {
        //二分法查询
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;

        // i太小
        if (i < iMax && nums2[j - 1] > nums1[i]) 
        {
            iMin = iMin + 1; // i is too small
        }

        // i太大
        else if (i > iMin && nums1[i - 1] > nums2[j]) 
        {
            iMax = iMax - 1; // i is too big
        }

        // i合适
        else 
        { 
            int maxLeft = 0;
            //若i为0即，nums1左侧划分的是没有值的，左侧的最大值即为num2[j-1]
            if (i == 0) 
            { 
                maxLeft = nums2[j - 1]; 
            }
            //同理j=0
            else if (j == 0) 
            { 
                maxLeft = nums1[i - 1]; 
            }
            //否则取num2[j-1]与nums1[i - 1]的大值作为左边的值
            else
            { 
                maxLeft = (nums1[i - 1]>nums2[j - 1])?nums1[i-1]:nums2[j-1];
            }
            //两容器之和为奇数，中位数为maxLeft
            if ((m + n) % 2 == 1) 
            { 
                return maxLeft; 
            }
			
            //两容器之和为偶数，中位数为（maxLeft+minRight）/2
            int minRight = 0;
            //i=m，即nums1右侧无划分，右侧的小值取nums2[j]
            if (i == m) 
            { 
                minRight = nums2[j]; 
            }
            //同理j=n
            else if (j == n) 
            { 
                minRight = nums1[i];
            }
            //否则取num2[j]与nums1[i ]的小值作为右边的值
            else 
            { 
                minRight = (nums2[j] < nums1[i]) ? nums2[j] : nums1[i];
            }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;


}

复杂度分析：

  • 时间复杂度：$O(\log(\min(m,n)))$。

    首先，查找的区间是[0,m]。而该区间的长度在每次循环之后都会减少为原来的一半。 所以，我们只需要执行 $\log(m)$次循环。由于我们在每次循环中进行常量次数的操作，所以时间复杂度为 $O(\log(m))$。由于$m \leq n$,所以时间复杂度是$O(\log(\min(m,n)))$。

  • 空间复杂度:$O(1)$,只需要恒定的内存来存储 9 个局部变量.