【leetcode刷题笔记】004.Median of Two Sorted Arrays

日期：20180911

题目描述：

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.

Examples：

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

详解：

这道题以为必须用到什么高端方法，不然肯定会超时，自己编了半天总调不通，最后干脆不调了，直接看了答案，发现很简单粗暴，也不会超时。

就不再过多的深究最完美的算法了，毕竟现在找工作紧迫，没有时间和每一道题死磕，先混个脸熟。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<double>v;
        int m=nums1.size(),n=nums2.size();
        double median=0;
        for(int i=0;i<m;i++)
            v.push_back(nums1[i]);
        for(int i=0;i<n;i++)
            v.push_back(nums2[i]);
        sort(v.begin(),v.end()); //用了c++自带的sort
        int avg=(n+m)/2;
        if((m+n)%2==0) median=(v[avg-1]+v[avg])/2;
        else  median=v[avg];
        return median;
    }
};

总结：

在比赛或笔试中，自己写的快排往往没有自带的sort快，更不用说冒泡啥的了。所以特地总结一下C++中的sort的使用方法：

• sort必须的头文件#include < algorithm>然后需要using namespace std;

• 它使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)。

• sort函数有三个参数：（第三个参数可不写，默认为升序）

  • 待排序数组的起始地址

  • 待排序数组的结束地址，vector可以用sort(a.begin(),a.end())，数组可以用sort(a,a+10)，这里假设长度为10（注意不是a+9）。

  • 最后一个参数为比较函数，可以重新编写cmp函数：

    bool cmp（int a,int b）{
    　　return a>b;
    }
    

    也可以通过现有的模板比较函数：equal_to<Type>、not_equal_to<Type>、greater<Type>、greater_equal<Type>、less<Type>、less_equal<Type>。例如：

    sort(a,a+20,greater<int>());