Leetcode004

LeetCode004：寻找两个有序数组的中位数         给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。

示例 1:
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

解法一：基于push_back和sort的方法 (执行用时：36ms，内存消耗7.9MB)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int Size1 = int(nums1.size());
        int Size2 = int(nums2.size());
        int lensum = Size1 + Size2;
        double answer=0;
        for (int i = 0; i<Size2; i++)
        {
            nums1.push_back(nums2[i]);
        }
        sort(nums1.begin(), nums1.end());

        if (lensum % 2 == 1)
        {
            answer = nums1[lensum / 2];
            return answer;

        }

        else if (lensum % 2 == 0)
        {
            lensum = lensum / 2;
            answer = nums1[lensum];
            lensum -= 1;
            answer += nums1[lensum];
            answer /= 2;
            return  answer;

        }
        return answer;
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> nums1, nums2;
    int Size1, Size2;
    cout << "请输入数组nums1的大小： "<< endl;
    cin >> Size1;
    cout << "请输入数组nums1的元素： " << endl;
    int Currval;
    for (int i = 0; i < Size1; i++)
    {
        cin >> Currval;
        nums1.push_back(Currval);
    }
    cout << "请输入数组nums2的大小： " << endl;
    cin >> Size2;
    cout << "请输入数组nums2的元素： " << endl;
    int Currval2;
    for (int i = 0; i < Size1; i++)
    {
        cin >> Currval2;
        nums1.push_back(Currval2);
    }

    Solution a;
    cout << "数组nums1和nums2的中位数为： " << a.findMedianSortedArrays(nums1, nums2) << endl;

    system("pause");
    return 0;
}