【记录帖】(No.004)从零打卡刷Leetcode

写在前边:

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!欢迎小伙伴们把自己的思路在留言区分享出来噢!坚持打卡!


No.4 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))..

题目大意:给出两个有序的数字列表,长度分别为m,n。找到这两个列表中的中间值。(第一次出现了时间复杂度的要求噢)

例如:

#例子一:总长度为奇数
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
#例子二:总长度为偶数
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

仔细分析题目,nums1和nums2都已经是排好序了的,这就大大的降低了难度,让找到两个列表的中间值,其实我们可以拓展为找到两个列表的第k个值。当然这个是拓展部分了,对于这个题目,有不同的思路,最简单粗暴的就是将两个列表合并,之后进行排序,拍好序后进行寻找中间值就简单了。但是用传统的先合并再排序,效率想必会很低~

我们发现对于两个已经有序的列表(从小到大),其实有一个更优的排序方式:从小到大,依次进行列表元素的比较(为方便表述,小詹称两个列表为A,B),较小值放到一个新列表中,比如A中该位置的值较小,将其放到新的列表C中,同时将A列表下一个值继续与B中当前位置元素进行比较,以此类推。这样的比较次数就比先合并在排序小很多啦!代码如下:

def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        #创建新列表,并将所有元素初始为0
        nums3 = [0] * (len(nums1)+len(nums2))
        #指定三个列表的索引,初始值为0
        l_i,r_i,i = 0,0,0
        #当输入两个列表都还存在元素没进行比较的时候,循环进行对比
        #并将较小值放入新列表,同时较小元素的列表和新列表索引加一
        while(l_i < len(nums1)) and (r_i < len(nums2)):
            if nums1[l_i] < nums2[r_i]:
                nums3[i] = nums1[l_i]
                l_i += 1
            else:
                nums3[i] = nums2[r_i]
                r_i += 1
            i += 1
        #当存在某一个列表所有元素已经比较完,即拍好了序
        #剩下那个列表剩下的值直接放入新列表对应位置即可
        if l_i != len(nums1):
            nums3[i:] = nums1[l_i:]
        else:
            nums3[i:] = nums2[r_i:]
        #小詹有话说:注意‘/’和‘//’的区别
        #前者结果为float类型,后者为整除,结果为int型
        len_3 = len(nums3)
        #‘%’为取模运算,即看长度是否被2整除,即看偶数还是奇数
        if len_3 %2 != 0:
            return float(nums3[(len_3-1)//2])
        return (nums3[len_3//2 - 1]+nums3[len_3//2])/2

代码里,小詹已经添加了十分详细的注释,配上思路分析应该没有问题啦!这是第4篇打卡记录,都说三分钟热度,我看还有多少人坚持哈,还在坚持一起打卡的点个赞呗?

往期推荐

休息是为了走更远的路!

【记录帖】(No.003)从零打卡刷Leetcode

【记录帖】(No.002)从零打卡刷Leetcode

【记录帖】(No.001)从零打卡刷Leetcode

反爬虫和反反爬虫(下篇)

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-06-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:面向对象语法二(入门版)

1526
来自专栏青玉伏案

算法导论之插入排序和归并排序

  作为一名前线的码农不时地看一下算法和数据结构还是很有必要的,虽然《算法导论》这本书很难啃,但还是有必要啃一下的。算法这东西和某种编程语言关系不大,在大学的课...

2407
来自专栏逸鹏说道

我为NET狂官方面试题-基础篇

最近帮人过一遍C#基础,出了点题目,有需要的同志拿走 答案不唯一,官方答案只供参考,若有错误欢迎提出~ 答案明天发 面向过程 99乘法表 ? 用循环来输出以...

3299
来自专栏屈定‘s Blog

算法回顾--如何写递归?

总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

3542
来自专栏黑泽君的专栏

java基础和面向对象面试题_01

1872
来自专栏程序员的碎碎念

Unicode?utf-8?GB2312?

分享一点关于字符编码的来源的知识,是前段时间在廖雪峰老师的python教程里看到的,觉得很通俗易懂,现在复制了过来分享给各位没看过这个教程的朋友们。Unico...

4569
来自专栏Golang语言社区

go(golang)中的类型转换

在使用 go 这样的强类型语言时,我们常常会遇到类型转换的问题。比如 int 类型转 int64,interface{} 转 struct ,对一种类型取指针、...

90910
来自专栏恰童鞋骚年

《代码的未来》读书笔记:也谈闭包

  原文中使用了C语言的函数对象,这里我们主要从.NET平台来说。在.NET中,委托这个概念对C++程序员来说并不陌生,因为它和C++中的函数指针非常类似,很多...

1032
来自专栏hbbliyong

看到他我一下子就悟了-- 泛型(2)

   先说些题外话,只所以写这些东西。是看了CSDN上的曹版主的一篇:手把手教编程,不知道有没有人愿意参与。说实话,我工作四年,总感觉晕晕乎乎的,好多技术都 懂...

2999
来自专栏技术/开源

从C#到TypeScript - 高级类型

C# vs TypeScript - 高级类型 上一篇讲了基础类型,基本上用基础类型足够开发了,不过如果要更高效的开发,还是要看下高级类型,这篇和C#共同点并不...

2189

扫码关注云+社区

领取腾讯云代金券