寻找两个有序数组的中位数

该题目如果使用时间复杂度为O（m+n）的算法则会非常简单，今天我们在这里介绍一个时间复杂度为O（log(m+n)）的算法。

我们这里采用二分法的思想去解决这道题目，首先我们给出的数组是两个有序数组，这样的话，我们可以很方便的将两个数组各自分为两个部分，而我们要寻找的中位数只需要将两个数组合并后的数组分为等长两部分，并且左边的最大值小于右边的最小值即可。那么我们可以先满足第一个条件，再去寻找满足第二个条件的 将两个数组各自分为两个部分 的分割方式，找到之后，我们便可以轻而易举的给出中位数的数值。程序代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2);
int main()
{
    int len_1, len_2;
    cin >> len_1 >> len_2;
    vector<int> nums1(len_1);
    vector<int> nums2(len_2);
    for (int i = 0; i < len_1; ++i)
    {
        cin >> nums1[i];
    }
    for (int i = 0; i < len_2; ++i)
    {
        cin >> nums2[i];
    }
    cout << findMedianSortedArrays(nums1, nums2);
    return 0;
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
{
    int m = nums1.size();
    int n = nums2.size();
    vector<int> temps1;
    vector<int> temps2;
    if (m > n)
    {
        temps1 = nums2;
        temps2 = nums1;
        int tmp = m; m = n; n = tmp;
    }
    else
    {
        temps1 = nums1;
        temps2 = nums2;
    }
    int iMin = 0, iMax = m, halflen = (m + n + 1) / 2;
    //以上步骤保证数组1短于数组2，这样数组1中的任意一种分法在数组2中都成立。
    while (iMin <= iMax)
    {
        int i = (iMin + iMax) / 2;
        int j = halflen - i;//因为m<=n,所以j可以直接赋值成halflen - i
        if (i < iMax && temps2[j - 1] > temps1[i]) 
        {
            iMin = i + 1; // i is too small
        }
        else if (i > iMin && temps1[i - 1] > temps2[j]) 
        {
            iMax = i - 1; // i is too big
        }
        //以上步骤是是实现二分法的关键代码，每次二分寻找合适的i值。
        else 
        { // i is perfect
            double maxLeft = 0;

            if (i == 0) 
            { 
                maxLeft = temps2[j - 1]; 
                //nums1左边部分没有元素，因此左边最大的是nums2的左边部分的最后一个元素
            }
            else if (j == 0) 
            { 
                maxLeft = temps1[i - 1]; 
                //nums2左边部分没有元素，因此左边最大的是nums1的左边部分的最后一个元素
            }
            else 
            { 
                maxLeft = max(temps1[i - 1], temps2[j - 1]); 
                //nums1左边部分和nums2左边部分都有元素，取最大值
            }
            if ((m + n) % 2 == 1) 
            { 
                return maxLeft; 
                //如果是奇数就直接返回该值
            }

            double minRight = 0;

            if (i == m) 
            { 
                minRight = temps2[j]; 
            }
            else if (j == n) 
            { 
                minRight = temps1[i]; 
            }
            else 
            { 
                minRight = min(temps2[j], temps1[i]); 
            }

            return (maxLeft + minRight) / 2;
            //如果是偶数就取两个数加和除以2
        }
    }
    return 0;
}

 

原文链接:https://www.cnblogs.com/gxyssd/p/12666374.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有