median of sorted arrays(排序数组中位数)

本文首发于我的公众号：码农手札，主要介绍linux下c++开发的知识包括网络编程的知识同时也会介绍一些有趣的算法题，欢迎大家关注，利用碎片时间学习一些编程知识，冰冻三尺非一日之寒，让我们一起加油！

前言

median of sorted arrays排序数组的中位数，相信大家基本都听说过这道题的大名，一般面试的话面试官想要加大难度这道题是个很好的选择，说实话这道题我一直是很有畏惧感的，因为我觉得这道题的解法相对不直观甚至不太方便记忆，但是难啃的骨头最终也是要啃的，所以今天我花了大半天的时间来学习一下这个问题，同时参考了一些大神的想法，写出了此篇博客

题目

给定两个已经排好序的数组A1和A2，其长度分别为m和n，找到这两个数组合并之后得到的数组的中位数，要求时间复杂度为O(log(m+n))

思路

我觉得这道题一般的解法有两种：

1. 第一种是利用中位数在合并后数组中的位置，由于两个数组的长度分别为m和n，为了解释方便假设m+n为奇数，不妨设2*k+1=m+n，这个时候合并数组的中位数就是合并数组中第k大的数字（第k小也是一样），这个时候一些解法会通过不断削减两个数组的长度，最终找到期望的数字，这个方法一般做出来的时间复杂度就是O(log(m+n))，

2. 第二种方法我觉得要更聪明，这个用到了二分查找的思想，先选择两个数组中长度更小的一个，假设这个数组为A1，然后找到合适的分割位置，假设分割线左边最大的数字为L1，分割线右边最小的数字为R1，然后再找另外一个数组假设为A2的分割位置，实际上这个分割位置是确定的，因为A2的分割位置和A1的分割位置是有关系的（后面会讲到两个分割位置之和为一个数），所以这个时候A2的分割位置实际上是不需要寻找的，再假设A2分割线左边最大的数字为L2，分割线右边最小的数字为R2，同时满足两个分割线左边的任意元素都小于等于两个分割线右边的任意元素，这个条件看着唬人，其实等价于:

   L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2

   而由于数组是有序的，那么必然有L1 <= R1 && L2 <= R2, 所以最终只需要满足L1 <= R2 && L2 <= R1即可，如果满足了这两个条件，由于两个分割线左右数字数量相等，所以中位数实际上就是(max(L1,L2) + min(R1,R2))/2.0，写到这里，可能大家会有疑问，万一合并数组的总长度为奇数，那么两个分割线的左右数字总量肯定不相等啊，不要急，后面会有解释

具体解释

我记得我最早做这个问题的时候，被数组长度的奇偶性折腾的够呛，简直想分开处理这些情况了，但是这次既然咱们是二战这个问题，那么必然不会采用分开处理的方式，不然岂不是落了下乘（笑），那么我们的问题来了，如何屏蔽数组长度的奇偶性对我们的影响呢，聪明的读者应该能够想到，我们采用补数字的方式，对于数组的每个数字我们都复制一遍，这样每个数组的长度都是偶数，同时合并数组的长度也是偶数，例子如下：

A1: 1 2 3 4 5
A2: 1 1 1 1 1 1

经过我们的补数字之后，数组变成了这样：

B1: 1 1 2 2 3 3 4 4 5 5
B2: 1 1 1 1 1 1 1 1 1 1 1 1

这个时候，问题就变得简单了起来，总共有2m+2n个数字，所以两个分割线左边的数字长度之和为m+n，我们假设在数组B1中选择的分割线左边的数字长度为c1，那么在B2选择的分割线右边的数字长度为c2，并且c1+c2=m+n，现在就是确定L1，L2，R1和R2了，在B1和B2里面，这个不是问题，我们不妨假设c1为5，那么c2=5+6-5=6，在上面给出的例子中

L1 = B1[5-1] = 3
R1 = B1[5] = 3
L2 = B2[6-1] = 1
R2 = B2[6] = 1

这个时候，由于并不满足条件L1 <= R2 && L2 <= R1，所以说明我们的分割线选的不合适，还需要继续寻找，所以这个实际上就是二分查找合适分割线的问题，所以时间复杂度为log(min(m,n))

小优化

上面的例子我们是通过补数字的方式来解决问题的，那么能否再优化一下，做到直接利用原数组呢，这个问题就需要我们观察补了数字的数组的索引了，通过上面的例子，我们可以看到数组B中元素到数组A中的映射关系是，B[I] = A[I/2]，I为B中任意一个数字的索引，所以现在问题变得简单了起来，我直接给出结论：

L1 = A1[(c1-1)/2]
R1 = A1[c1/2]
L2 = A2[(c2-1)/2]
R2 = A2[c2/2]

到现在问题基本已经解决了，个人觉得这个解释思路还算清楚

代码

下面给出最终版本的代码：

double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    const int size1 = nums1.size(), size2 = nums2.size();
    if (size1 > size2)
      return findMedianSortedArrays(nums2, nums1);
    ///lo为c1取值的下限，也就是0，hi为c1取值的上限，也就是2*size1（其实就是上面的2*min(m,n))
    int lo = 0, hi = 2 * size1;
    while (lo <= hi) {
      int c1 = (lo + hi) / 2;
      int c2 = size1 + size2 - c1;
      ///下面L1和L2取INT_MIN说明分割线左边没有元素了，直接取INT_MIN
      int L1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
      int L2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
      ///下面R1和R2取INT_MAX说明分割线右边没有元素了，直接取INT_MAX
      int R1 = (c1 == 2 * size1) ? INT_MAX : nums1[c1 / 2];
      int R2 = (c2 == 2 * size2) ? INT_MAX : nums2[c2 / 2];
      if (L1 > R2)
        hi = c1 - 1;///这个说明我们分割线选的靠右了，导致L1太大，所以将上限向左移
      else if (L2 > R1)
        lo = c1 + 1;///这个说明我们分割线选的靠左了，导致R1太小，所以将下限向右移
      else
        return (max(L1, L2) + min(R1, R2)) / 2.0;
    }
    return -1;
  }

总结

总的来说，我觉得这道题是个非常不错的题目，在leetcode中对得起hard的难度，首先我们需要想到使用两条分割线使得两个数组分割线左边和两条分割线右边的数组长度之和相同，这点已经不容易了，当我们想到这一步，我们还需要想到合适的办法来解决数组长度对我们解题的影响，我给出的这个办法是我参考leetcode题解的大神思路想出来的，他的思路是使用#来对数组进行补全，也是非常棒的方法，我的思路也是受他的启发，在这里也得感谢他的分享，以上。