前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 4 Median of Two Sorted Arrays

LeetCode 4 Median of Two Sorted Arrays

作者头像
ShenduCC
发布2018-12-07 17:29:28
2540
发布2018-12-07 17:29:28
举报
文章被收录于专栏:算法修养算法修养算法修养

LeetCode 1004

思路

一开始我用快速排序将两个数组重新排序,居然超时。 其实两个已经排好的数组用一个for循环排序就好了,效率O(m+n) ,而快排是O((m+n)*log(m+n))

但是题目上给的是O(log(m+n))的效率,应该是把O(m+n)都放过了。

class Solution {
public:
    int a[1000005];
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        int n=nums1.size();
        int m=nums2.size();
        int i=0,j=0;
        int tag=0;
        while(i<n&&j<m)
        {
           if(nums1[i]<=nums2[j])
                a[tag++]=nums1[i++];
           else 
               a[tag++]=nums2[j++];
        }
        while(i<n)
        {
            a[tag++]=nums1[i++];
        }
        while(j<m)
        {
            a[tag++]=nums2[j++];
        }
        
        if((n+m)%2==0)
            return 0.5*(a[(n+m)/2]+a[(n+m)/2-1]);
        else
            return 1.0*a[(n+m)/2];   
    }
    
    
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-11-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档