[LeetCode] 4、寻找两个有序数组的中位数

题目描述

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

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
           

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5
           

解题思路

最直接的想法是先合并两个有序数组，然后再找其中位数，但是这样时间复杂度就是 O ( m + n ) O(m + n) O(m+n)，不满足题意。（常见题，要会）

• 割：（太繁琐，不推荐，不用看）为保证时间复杂度，要运用官方题解中“割”和“第k个元素”的概念，我们设：

  Ci

  为第

  i

  个数组的割，

  LMaxi

  为第

  i

  个数组割后的左最大元素，

  RMini

  为第

  i

  个数组割后的右最小元素。

  注：割可以割在两个数中间，也可以割在1个数上，如果割在一个数上，那么这个数即属于左边，也属于右边，此时

  LMax1 == RMin1

  。

  首先，

  LMax1<=RMin1，LMax2<=RMin2

  这是肯定的，因为数组是有序的，左边肯定小于右边！而如果割(

  Cut

  )在某个数上，则左右相等。

  其次，如果我们让**

  LMax1<=RMin2，LMax2<=RMin1

  ** ，那么左半边全小于右半边，

  如果左边的元素个数相加刚好等于k, 那么第k个元素就是Max(LMax1, LMax2)

  ，这是比较好理解的。

  

  那么如果

  LMax1>RMin2

  ，说明数组1的左边元素太大（多），我们把

  C1

  减小（即数组1的割的位置左移），

  C2=k-C1

  也就相应的增大。

  LMax2>RMin1

  同理，把

  C2

  减小，

  C1=k-C2

  也就相应的增大。

  需要考虑的问题：两个数组的最大问题是，它们合并后，

  m+n

  总数可能为奇，也可能为偶，所以我们得想法让

  m+n

  总是偶数。通过虚拟加入

  ‘#’

  （其实根本没这一步），我们让

  m

  转换成

  2m+1

  ，

  n

  转换成

  2n+1

  , 两数之和就变成了

  2m+2n+2

  ，恒为偶数。通过下面的转换，我们可以保证虚拟加

  #

  后每个元素跟原来的元素一一对应：

  

  而对于割(

  Cut

  )，如果割在

  ‘#’

  上等于割在2个元素之间，割在数字上等于把数字划到2个部分（此时

  LMax1 == RMin1

  ），总是有以下成立：

  LMaxi = (Ci-1)/2 位置上的元素
  RMini = Ci/2 位置上的元素
             

  最快的割(

  Cut

  )是使用二分法：

  • LMax1>RMin2

    ，把

    C1

    减小，

    C2

    增大。—>

    C1

    向左二分；

  • LMax2>RMin1

    ，把

    C1

    增大，

    C2

    减小。—>

    C1

    向右二分；
  如果

  C1

  或

  C2

  已经到头了怎么办？这种情况出现在：

  如果有个数组完全小于或大于中值

  。 可能有4种情况：

  • C1 = 0

    —— 数组1整体都在右边了，所以都比中值大，中值在数组2中，简单的说就是数组1割后的左边是空了，所以我们可以假定

    LMax1 = INT_MIN

    ；

  • C1 =2n

    —— 数组1整体都在左边了，所以都比中值小，中值在数组2中 ，简单的说就是数组1割后的右边是空了，所以我们可以假定

    RMin1= INT_MAX

    ，来保证

    LMax2<RMin1

    恒成立；

  • C2 = 0

    —— 数组2整体在右边了，所以都比中值大，中值在数组1中 ，简单的说就是数组2割后的左边是空了，所以我们可以假定

    LMax2 = INT_MIN

    ；

  • C2 = 2m

    —— 数组2整体在左边了，所以都比中值小，中值在数组1中, 简单的说就是数组2割后的右边是空了，为了让

    LMax1 < RMin2

    恒成立，我们可以假定

    RMin2 = INT_MAX

    ；

  rMax1 = (c1 == 0)? INT_MIN: nums1[(c1-1) / 2];
  lMIn1 = (c1 == 2*length1)? INT_MAX: nums1[c1/2];
  rMax2 = (c2 == 0)? INT_MIN: nums2[(c2-1) / 2];
  lMin2 = (c2 == 2*length2)? INT_MAX: nums2[c2/2];
             

  最后

  return (max(rMax1, rMax2) + min(lMIn1, lMin2)) / 2.0;

  即可。

• 第K小的数（只关注解法3，骚操作，推荐！！！）：

  看到

  log

  ，很明显，我们只有用到二分的方法才能达到。我么可以将求中位数转换为求第K小的数字的问题。假设我们要找第

  k

  小数，由于数列是有序的，所以我们可以每次循环排除掉

  k/2

  个数。（图示见题解）

  更一般的情况

  A[1]

  ，

  A[2]

  ，

  A[3]

  ，

  A[k/2]

  … 和

  B[1]

  ，

  B[2]

  ，

  B[3]

  ，

  B[k/2]

  … ，如果

  A[k/2]

  <

  B[k/2]

  ，那么

  A[1]

  ，

  A[2]

  ，

  A[3]

  ，

  A[k/2]

  都不可能是第

  k

  小的数字 => 用新生成的两个新数组进行递归找第k小的数字。

  要注意一点，由于我们每次都是取

  k/2

  的数进行比较，有时候可能会遇到数组长度小于

  k/2

  的时候。所以我们需要每次都比较

  start_i + min(k/2, 新数组长度) - 1

  对应的数字。（特例）

  

  此时

  k / 2

  等于

  3

  ，而上边的数组长度是

  2

  ，我们此时将箭头指向它的末尾就可以了。这样的话，由于

  2 < 3

  ，所以就会导致上边的数组

  1，2

  都被排除。造成下边的情况。

  

  递归出口有两种情况：(递归出口就是当

  k=1

  或者其中一个数字长度是 )
  • 例如

    nums1

    为空时（

    len1 == 0

    ），直接返回

    nums2

    的第

    k

    个数字。

  • k == 1

    时，返回

    min(nums1[start1], nums2[start2])

    （

    k

    最后一定会等于

    1

    ）。

参考代码

法一

“割”的思路，不推荐

#include<bits/stdc++.h>
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 length1 = nums1.size();
        int length2 = nums2.size();
        if(length1 == 0 && length2 == 0)
            return 0.0;

        // 对短的数组二分（更快），见到log时间复杂度，考虑二分。
        if(length1 > length2)
            return findMedianSortedArrays(nums2, nums1);

        // 我们目前是虚拟加了'#'，所以数组1是2*n+1长度。
        int low = 0, high = 2*length1;
        // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。
        // LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
        int rMax1, lMIn1, rMax2, lMin2;
        while(low <= high){
            // 二分结果，相当于mid。
            int c1 = (low + high) >> 1;
            // 清晰易懂，c2 = m + n - c1; 我的理解是 c2和c1都是割在位置上的，所以c1左边会有 c1+0.5个位置，同理c2左边会有c2+0.5个位置，
            // 而我们做c2和c1分割的目的就是让c2、c1的左边有m+n+1个位置，右边也有m+n+1个位置，所以 c2+0.5+c1+0.5=m+n+1；所以有c2 = m + n - c1;
            int c2 =  length1 + length2 - c1;

            // 要考虑四种特殊情况（如果有个数组完全小于或大于中值）
            rMax1 = (c1 == 0)? INT_MIN: nums1[(c1-1) / 2];
            lMIn1 = (c1 == 2*length1)? INT_MAX: nums1[c1/2];
            rMax2 = (c2 == 0)? INT_MIN: nums2[(c2-1) / 2];
            lMin2 = (c2 == 2*length2)? INT_MAX: nums2[c2/2];

            // LMax1>RMin2，把C1减小，C2增大。—> C1向左二分
            // LMax2>RMin1，把C1增大，C2减小。—> C1向右二分
            if(rMax1 > lMin2)
                high = c1 - 1;
            else if(rMax2 > lMIn1)
                low = c1 + 1;
            else      // 已经找到了合适的切割位置
                break;
        }

        return (max(rMax1, rMax2) + min(lMIn1, lMin2)) / 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);
	printf("%f\n", ret);
	return 0;
}

           

法二（推荐，找中位数转换为找第K小的数）

// 求中位数，其实就是求第 k 小数的一种特殊情况，而求第 k 小数有一种算法。（一次去掉一部分）
// 无论是找第奇数个还是第偶数个数字，对我们的算法并没有影响，而且在算法进行中，
// k的值都有可能从奇数变为偶数，最终都会变为1，或者由于一个数组空了，直接返回结果。
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        if(len1 == 0 && len2 == 0)
            return 0.0;

        // 第几小的数，从1开始算。
        int posOfLeft = (len1 + len2 + 1) / 2;
        int posOfRight = (len1 + len2 + 2) / 2;

        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的k。
        return (getKthRecursively(nums1, 0, len1-1, nums2, 0, len2-1, posOfLeft) +
                getKthRecursively(nums1, 0, len1-1, nums2, 0, len2-1, posOfRight)) / 2.0;
    }

    double getKthRecursively(vector<int> &nums1, int start1, int end1,
                             vector<int> &nums2, int start2, int end2, int k){
        // 当前两个数组中剩余数字的个数/长度。（这个数字一直在变，所以不能当做参数传递，需每次重新计算）
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //保证如果有数组空了，保证一定是nums1为空。（其实这一句不需要，下面再加个 len2 == 0 的判断条件就可以了）
        if(len1 > len2)
            return getKthRecursively(nums2, start2, end2, nums1, start1, end1, k);

        // 递归出口：num1为空，此时直接返回nums2的第k个数字即可；
        // 或者只需要找nums1和nums2中的第1小的数字时并min()，直接返回即可。（k的值最后一定会变为1）
        if(len1 == 0)
            return nums2[start2 + k - 1];
        if(k == 1)
            return min(nums1[start1], nums2[start2]);

        // 要在两个数组中比较的位置下标。
        // 我们每次都是取 k/2 个数字进行比较，有时候可能会遇到数组长度小于 k/2的时候，此时比较最后一个数字。
        int comparePos1 = start1 + min(len1, k/2) - 1;
        int comparePos2 = start2 + min(len2, k/2) - 1;
        if(nums1[comparePos1] > nums2[comparePos2])
            return getKthRecursively(nums1, start1, end1, nums2, comparePos2 + 1, end2, k - (comparePos2 - start2 + 1));
        else
            return getKthRecursively(nums1, comparePos1 + 1, end1, nums2, start2, end2, k - (comparePos1 - start1 + 1));
    }

};