当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 寻找两个有序数组的中位数

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

2020年04月09日  | 移动技术网IT编程  | 我要评论

铁流之奉系军阀,影视广告价格,魅力研习社第160期

该题目如果使用时间复杂度为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;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网