减治法：寻找两个正序数组的中位数

﹏ヽ暗。殇╰゛Y 2022-11-29 12:29 44阅读 0赞

## 一、问题描述 ##

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

示例1

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

示例2

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

## 二、解法 ##

### 1. 解法一：遍历法 ###

不妨设数组1的长度为n1，数组2的长度为n2， 记  n = n 1 + n 2 n=n\_1+n\_2 n=n1\+n2

如果两个数组重新排序组合在一起，那么我们知道：

当 n 为奇数时，中位数为组合数组的第 n 2 + 1 \\frac\{n\}\{2\}+1 2n\+1个数，它在数组中的下标应该是 n 2 \\frac\{n\}\{2\} 2n

当 n 为偶数时，中位数为组合数组的第 n 2 、 n 2 + 1 \\frac\{n\}\{2\}、\\frac\{n\}\{2\}+1 2n、2n\+1个数的平均数，它们在数组中的下标应该是 n 2 − 1 、 n 2 \\frac\{n\}\{2\}-1、\\frac\{n\}\{2\} 2n−1、2n

现在我们的思路很简单：设置两个指针，按从小到大的顺序同时遍历两个数组，记住，数组中当前元素小于另一数组，该数组指针才向前移动。这样，当我们遍历到第第 n 2 + 1 \\frac\{n\}\{2\}+1 2n\+1个数时，即可求得中位数。这里还需要注意的时，偶数情况下，我们需要两个数，所以我们需要记录前一个遍历过的数是哪一个，所以我们设置pre和cur变量代表前一个遍历的数和当前遍历的数，最后将两者相加，即可得到n为偶数时的中位数。

代码如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
            int n1 = nums1.size();
            int n2 = nums2.size();
            int a=0,b=0;                        // 指针
            int n = n1 + n2;
            int pre = 0, cur = 0;            // 前一个数和当前数
            for(int i = 0; i<=n/2;i++)
            {
        
                pre = cur;
                if(a<n1&&(b>=n2||nums1[a]<=nums2[b]))
                {
        
                    cur = nums1[a++];
                }
                else
                {
        
                    cur = nums2[b++];
                }
            }
            if(n%2==0)
                return (pre+cur)/2.0;
            else
                return cur;
        }

**复杂度分析**

根据代码，我们很容易知道我们需要进行O((n1+n2)/2) = O(n1+n2)次遍历

### 2. 舍弃k/2法 ###

上面我们的方法时每一次遍历都舍弃一个不是第k个数的数，下面我们想要提高效率，就要想要每一次舍弃k/2个。这是怎么做到的呢？

![在这里插入图片描述][2020082021300432.png_pic_center]

如图所示， 我们要找到这两个数组组合后的第7个数，我们找到两个数组中第k/2个数进行比较，舍去小数所在数组的前k/2个数。以上图为例，数组2的3<4，所以我们舍弃数组2的前三个数。下面，我们在用新得到的两个数组求得第k-k/2的个数，最终，当k=1时，即可求得我们想要的中位数。

代码：

double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        
        int len1 = nums1.size();
        int len2 = nums2.size();
        int n = len1 + len2;
        int k = n / 2 + 1;
        if (n % 2 == 0)
            return (getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k) + getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k - 1)) / 2.0;
        else
            return getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k);
    }
    double getKth(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;
         //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2)
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0)
            return nums2[start2 + k - 1];
    
        if (k == 1)
            return min(nums1[start1], nums2[start2]);
    
        int i = start1 + min(k / 2, len1) - 1;
        int j = start2 + min(k / 2, len2) - 1;
        if (nums1[i] < nums2[j])
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        else
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    }

**算法性能分析**  
时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n）O(log(m+n）。

空间复杂度：虽然我们用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)O(1)。

## 三、总结 ##

其实第一种算法其实很容易想到，第二种算法用到了减治的思想，提高了效率。

## 四、参考资料 ##

1.  https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

[2020082021300432.png_pic_center]: /images/20221124/cc7f68924148449285c47142d5dac572.png