专栏首页苦逼的码农从0打卡leetcode之day 5 ---两个排序数组的中位数

从0打卡leetcode之day 5 ---两个排序数组的中位数

前言

我靠,才坚持了四天,就差点不想坚持了。不行啊,我得把leetcode上的题给刷完,不然怕是不好进入bat的大门。

题目描述

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

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

中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5``

解题

最简单粗暴的就是把这两个数组头尾连接起来,然后重新给他们排序一下,冒泡排序相信你信手拈来,当然,你也可以装逼用快速排序。

但是,如果这样子做的话,题目给你的有序数组就没啥用了,和无序一个样,所以这样做是不行的。题目要求是时间复杂度不能超过O(log(n+m)),说实话,这个复杂度我是不知道怎么做好,我的做法时间复杂度是O(n+m)。

具体是这样的

居然两个数组都是有序的了,我们可以再弄一个中间数组,然后把两个数组各自从数组头开始比较,哪个元素小,我们就把它存在中间数组。然后接下下一个元素一直比较下去。

我还是直接上代码吧。如下:

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int t = m + n;//总长度
            int temp[] = new int[t];
            int i  = 0, j = 0, k = 0;
            double obj;//用来存目标值

            while(i < m && j < n){
                //把数组中比较小的值转移到temp数组中
                if(nums1[i] < nums2[j]){
                    temp[k++] = nums1[i++];
                }else{
                    temp[k++] = nums2[j++];
                }
            }
            //把剩余的转移过去
        while (i < m){
                temp[k++] = nums1[i++];
        }
        while(j < n){
                temp[k++] = nums2[j++];
        }
        //两个数组的总个数是奇数还是偶数
        if(t % 2 == 0){//偶数
                obj = (temp[t/2] + temp[(t-1)/2]) / 2.0;
        }else{
                obj = temp[t/2];
        }

        return obj;
    }

虽然时间复杂度是O(n+m),但是提交的时候居然通过了,而且还打败了93%的人。

不过,这里还可以在优化,把时间复杂度降低到O((n+m)/2)。

就是说其实我们不用给整个temp数组排序,我们只要求出前面一半的数组元素就可以知道中间那个元素了,。例如不管一共是偶数个元素还是奇数个元素,我们让temp存到下标为t/2就可以了。然后再来判断t是奇数还是偶数…..

例如上面两个示例,示例1一共有三个元素,那么temp[t/2]=temp[1]=2。然后直接把temp[t/2]=temp[1]取出来返回就可以了。

示例2一共有4个元素,那么temp[t/2]=temp[2]=3。由于是偶数,我们直接把temp[t/2]=3和temp[t/2-1]=2这两个元素取出来处理之后返回就可以了。

至于代码这么写,我就不写了。知道有这么一回事就可以了。

如果你坚持想要O(log(n+m))的时间复杂度,那么可以看官方给的答案:

出问题了

本文分享自微信公众号 - 苦逼的码农(di201805),作者:帅地

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 三分钟基础:有哪些经典的进程调度算法?

    想当初,操作系统创造我时,只是打算让我用 FCFS 调度算法,简单维护下进程的秩序。但我后来的发展,远远超过了他的想象。

    帅地
  • 记一次面试:进程之间究竟有哪些通信方式? ---- 告别死记硬背

    有一次面试的时候,被问到进程之间有哪些通信方式,不过由于之前没深入思考且整理过,说的并不好。想必大家也都知道进程有哪些通信方式,可是我猜很多人都是靠着”背“来记...

    帅地
  • 头条二面智力题!难受!

    注意,下面是 n,不是 10。网上的题目好多是 1-10 楼。。。。应该都是被简化的,分析起来并不友好。

    帅地
  • LintCode-488.快乐数

    一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

    悠扬前奏
  • oeasy教你玩转linux010104灵魂之问whatis

    oeasy
  • python面向对象(2)—— 继承(2)

    在上一节中,我们重写了父类的方法,但是如果我们还想用这两个父类的方法,可按如下例子进行重写:

    gzq大数据
  • 命名实体识别新SOTA:改进Transformer模型

    TENER: Adapting Transformer Encoder for Name Entity Recognition

    AI科技评论
  • 1050. 螺旋矩阵(25)

    本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为m行n列,满足条...

    AI那点小事
  • 无法解析服务器的DNS地址

    背景: 打开浏览器突然之间发现无法上网了,提示说无法解析服务器的DNS地址 ? 原因: DNS,就是将域名转换为IP地址功能的服务器 DNS解析不了,是由于...

    运维小白
  • 谷歌,微软,阿里,美团实习生面经

    牛客网

扫码关注云+社区

领取腾讯云代金券