4寻找两个正序数组的中位数

不念不忘少年蓝@ 2023-02-27 13:31 36阅读 0赞

## 一、前言 ##

分类：Divide and Conquer。

问题来源LeetCode 4 难度：困难。

问题链接：[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

## 二、题目 ##

给定两个大小为 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(n+m)， 不符合题意要求。

方法二：二分查找两个有序数组的第K小元素。

找a和b两个有序数组中第K小，就是在a中找某个位置i，在b中找某个位置j，其满足条件为：

*  i + j = k
 *  a\[i - 1\] <= b\[j\] && b\[j - 1\] <= a\[i\]

第 K 小即为：max(a\[i - 1\], b\[j - 1\]);

**公式推导：**

1.  i + j = k
2.  0 <= i <= n
3.  0 <= j <= m ==> 0 <= k - i <= m ==> k - m <= i <= k ==> max(0, k - m) <= i <= min(k, m)
4.  i 通过二分查找即可。

**看图加深影响：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

## 四、思考题 ##

思考一个问题，方法二，通过二分查找 i 值即可确定 j 值，如果是在三个（或更多）升序数组中查找第 k 大的值呢？

方法二 i 值确定了 j 值也就可以确定，巧就巧在这里。如果是三个或三个以上的数组，就不那么好处理了。

## 五、 编码实现 ##

//==========================================================================
    /*
    * @file    : 004_FindMedianSortedArrays.h
    * @label   : Divide and Conquer
    * @blogs   : 
    * @author  : niebingyu
    * @date    : 2020/07/16
    * @title   : 4.寻找两个正序数组的中位数
    * @purpose : 给定两个大小为 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
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <stack>
    #include <unordered_map>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_FINDMEDIANSORTEDARRAYS namespace NAME_FINDMEDIANSORTEDARRAYS {
    #define NAMESPACE_FINDMEDIANSORTEDARRAYSEND }
    NAMESPACE_FINDMEDIANSORTEDARRAYS
    
    // 方法一： 归并之后找中间值
    // 时间复杂度: O(n+m)， 不符合题意要求
    class Solution_1 
    {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
        {
            vector<int> arr;
            arr.reserve(nums1.size() + nums2.size());
            int i1 = 0, i2 = 0;
            while (i1 < nums1.size() && i2 < nums2.size())
            {
                if (nums1[i1] <= nums2[i2])
                    arr.push_back(nums1[i1++]);
                else
                    arr.push_back(nums2[i2++]);
            }
    
            while (i1 < nums1.size()) arr.push_back(nums1[i1++]);
            while (i2 < nums2.size()) arr.push_back(nums2[i2++]);
    		
            // 数组为空
            if (arr.empty()) 
                return 0;
            
            // 判断数组长度是奇数还是偶数
            if ((arr.size() & 1) == 1) //奇数
                return arr[arr.size() >> 1];
            else
                return (arr[arr.size() / 2 - 1] + arr[arr.size() / 2]) / 2.0;
    
            return 0;
        }
    };
    
    // 方法二：二分查找两个有序数组的第K小元素
    // 时间复杂度：O(log(min(m,n))), 空间复杂度：O(1)
    class Solution_2 
    {
    public:
        int findKthElm(vector<int>& nums1, vector<int>& nums2, int k)
        {
            assert(1 <= k && k <= nums1.size() + nums2.size());
            // 时间复杂度 log(min(n,m));
            if (nums1.size() > nums2.size()) swap(nums1, nums2);
    
            int l = max(0, int(k - nums2.size()));
            int r = min(k, int(nums1.size()));
            while(l < r)
            {
                int m = l + (r - l) / 2;
                if(nums2[k - m - 1] > nums1[m]) l = m + 1;
                else r = m;
            }
    		
            // 循环结束时的位置le即为所求位置，第k小即为max(nums1[le-1]),nums2[k-le-1])，但是由于le可以为0、k,所以
            // le-1或者k-le-1可能不存在所以下面单独判断下
            int nums1LeftMax = l == 0 ? INT_MIN : nums1[l - 1];
            int nums2LeftMax = l == k ? INT_MIN : nums2[k - l - 1];
            return max(nums1LeftMax,nums2LeftMax);
        }
    
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
        {
            int n = nums1.size() + nums2.size();
            if(n & 1) 
                return findKthElm(nums1, nums2, (n >> 1) + 1);
            else
                return (findKthElm(nums1, nums2, n >> 1) + findKthElm(nums1, nums2, (n >> 1) + 1)) / 2.0;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums1, vector<int>& nums2, double expect)
    {
        Solution_1 s1;
        double result1 = s1.findMedianSortedArrays(nums1, nums2);
       
       Solution_1 s2;
       double result2 = s2.findMedianSortedArrays(nums1, nums2);
       if (abs(result1 - expect) < 0.000001 && abs(result2 - expect) < 0.000001)
           cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. expect: " << expect << " ,result1: " << result1 << " ,result2: " << result2 << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums1 = {};
        vector<int> nums2 = {};
        double expect = 0;
    
        test("Test1()", nums1, nums2, expect);
    }
    
    void Test2()
    {
        vector<int> nums1 = { 1 };
        vector<int> nums2 = { 1 };
        double expect = 1;
    
        test("Test2()", nums1, nums2, expect);
    }
    
    void Test3()
    {
        vector<int> nums1 = {1};
        vector<int> nums2 = {2,3};
        double expect = 2;
    
        test("Test3()", nums1, nums2, expect);
    }
    
    void Test4()
    {
        vector<int> nums1 = { 1,4 };
        vector<int> nums2 = { 2,3 };
        double expect = 2.5;
    
        test("Test4()", nums1, nums2, expect);
    }
    
    void Test5()
    {
        vector<int> nums1 = { 1,3,5,7,9,16 };
        vector<int> nums2 = { 2,4,6,8,10,11,12,13,14,15 };
        double expect = 8.5;
    
        test("Test5()", nums1, nums2, expect);
    }
    
    void Test6()
    {
        vector<int> nums1 = { 3 };
        vector<int> nums2 = { 1,2,4,5,6,7,8,9,10 };
        double expect = 5.5;
    
        test("Test6()", nums1, nums2, expect);
    }
    
    void Test7()
    {
        vector<int> nums1 = { 1,7,9 };
        vector<int> nums2 = { 2,3,4,5,6,8,10 };
        double expect = 5.5;
    
        test("Test7()", nums1, nums2, expect);
    }
    
    void Test8()
    {
        vector<int> nums1 = { 1,2,8,9 };
        vector<int> nums2 = { 3,4,5,6,7,10 };
        double expect = 5.5;
    
        test("Test8()", nums1, nums2, expect);
    }
    NAMESPACE_FINDMEDIANSORTEDARRAYSEND
    // 测试 用例 END
    //
    void FindMedianSortedArrays_Test()
    {
        cout << "------ start 4.寻找两个正序数组的中位数 ------" << endl;
        //NAME_FINDMEDIANSORTEDARRAYS::Test1();
        NAME_FINDMEDIANSORTEDARRAYS::Test2();
        NAME_FINDMEDIANSORTEDARRAYS::Test3();
        NAME_FINDMEDIANSORTEDARRAYS::Test4();
        NAME_FINDMEDIANSORTEDARRAYS::Test5();
        NAME_FINDMEDIANSORTEDARRAYS::Test6();
        NAME_FINDMEDIANSORTEDARRAYS::Test7();
        NAME_FINDMEDIANSORTEDARRAYS::Test8();
        cout << "------ end 4.寻找两个正序数组的中位数 ------" << endl;
    }

**执行结果：**

![20200717195154824.png][]

[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/0e38920503504b87a6653763f0206614.png
[20200717195154824.png]: https://img-blog.csdnimg.cn/20200717195154824.png