【Leetcode】4. 寻找两个有序数组的中位数C++(直接排序法)

2020/1/21 10:29:42 人评论 次浏览 分类:学习教程

在这里插入图片描述
在这里插入图片描述

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

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

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

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int s2 = nums2.size();
        double ans;

        for (int i = 0; i < s2; i++)
        {
            nums1.push_back(nums2[i]);
        }

        sort(nums1.begin(), nums1.end());

        int s1 = nums1.size();

        if (s1 % 2 == 1)
        {
            ans = nums1[s1 / 2];
        }
        else
        {
            ans = float(nums1[s1 / 2] + nums1[s1 / 2 - 1]) / 2;
        }
        return ans;
    }
};

int main(void)
{
    vector<int> nums1, nums2;
    int num;
    double median;
    Solution S;

    // 输入nums1
    while (true)
    {
        cin >> num;
        nums1.push_back(num);
        if (cin.get() == '\n')
            break;
    }

    //输入nums2
    while (true)
    {
        cin >> num;
        nums2.push_back(num);
        if (cin.get() == '\n')
            break;
    }

    median = S.findMedianSortedArrays(nums1, nums2);
    cout << median << endl;

    return 0;
}
Memory逆光
发布了64 篇原创文章 · 获赞 121 · 访问量 8995
私信 关注

上一篇:Qt>信号与槽机制

下一篇:CAN的报文格式

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->