Median of Two Sorted Arrays

2019-08-16 07:51:53来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Median of Two Sorted Arrays

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Code:

//
//  main.cpp
//  中位数
//
//  Created by mac on 2019/7/17.
//  Copyright ? 2019 mac. All rights reserved.
//

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double midenum;
        if (nums1.size()>0 && nums2.size()>0) {
            for (int i=0; i<nums2.size(); ++i) {
                nums1.push_back(nums2[i]);
            }
            sort(nums1.begin(), nums1.end());
            if (nums1.size()%2==0) {
                midenum=(double)((double)(nums1[nums1.size()/2])+(double)(nums1[nums1.size()/2-1]))/2;
            }else{
                midenum=nums1[nums1.size()/2];
            }
            
        }else if (nums1.size()>0){
            if (nums1.size()%2==0) {
               midenum=((double)(nums1[nums1.size()/2])+(double)(nums1[nums1.size()/2-1]))/2;
            }else{
                midenum=nums1[nums1.size()/2];
            }
        }else{
            if (nums2.size()%2==0) {
                midenum=((double)(nums2[nums2.size()/2])+(double)(nums2[nums2.size()/2-1]))/2;
            }else{
                midenum=nums2[nums2.size()/2];
            }
        }
        return midenum;
    }
};

int main(int argc, const char * argv[]) {
    vector<int> a,b;
//    a.push_back(1);
//    a.push_back(2);
    b.push_back(2);
    b.push_back(3);
    Solution so;
    cout<<so.findMedianSortedArrays(a, b)<<endl;
    return 0;
}

运行结果

2.5
Program ended with exit code: 0

参考文献

  • https://leetcode.com/problems/median-of-two-sorted-arrays/

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

标签:

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

上一篇:二分法(一):二分法的基本思想

下一篇:C++ 继承 - 在派生类中对基类初始化