python中的min和in用代码实现
min
在 Python 中 min 函数可以直接返回列表中的最小项。
现在用代码演示一下,怎么用代码实现在列表中检索一个最小项。
def fn(L): MinIndex = 0 CurrentInder = 1 while CurrentInder < len(L): if L[MinIndex] > L[CurrentInder]: MinIndex = CurrentInder CurrentInder += 1 return L[MinIndex] L = [21,45,2,3,5,2,57,6,4] print(fn(L))
解释一下
先把列表的第一项,也就是索引为0的值置为最小项,然后跟第二项,也就是索引为1的值进行比较,设置while循环,退出条件是列表的每一项都比较完。这样遍历了整个列表,最小项的索引也就找到了。
那最大项的索引岂不是改个条件就获取了,没错。试一下吧。
in
在python 中 in 的运算符用于在列表中搜索一个特定的项,这个列表没有要求。那这个in方法用代码实现起来就比较简单了。
def fn(L,target): position = 0 while position < len(L): if L[position] == target: return ('索引是:{},值是:{}'.format(position,L[position])) position +=1 return -1 L = [21,45,1,3,5,2,57,6,4] print(fn(L,4))
只要挨个比较目标值就完事了。假如目标值不在列表中返回 -1 好了
但要考虑一件事,顺序搜索列表的性能怎么样呢?
- 在最好的情况下,目标值正好在列表的前面,算法只进行了一次迭代就找到了目标值,复杂度为O(1)。
- 最坏的情况下,目标项在列表的最末尾或者不在列表里,我们要比较n次(假如列表长度为n),那么最坏情况下,顺序搜索的复杂度为O(n)。
- 再来考虑一下平均情况下的算法复杂度。要确定平均情况下,把在每一个可能的位置找到目标项所需的迭代次数相加,总和除以n,这样一算,算法执行了(n+n-1+n-2+ ++1)/2 或者 (n+1)/ 2 次迭代。对于很大的n ,常数因子2的作用不大,因此,平均情况下的复杂度仍然为O(n).
得出结论,顺序搜索最好情况的性能很少见,而平均情况和最坏情况的性能则基本相同。
对于没有按照任何顺序排列的数据,顺序搜索是必要的,当列表有序的时候,可以使用二叉搜索,又称二分查找。
二分查找
假设列表中的项都是按照升序排列的,二分查找就是先找到中间一项跟目标项进行比较,如果相等就返回该项的位置,也就是索引。否则,如果目标项比列表中间项大,就在中间项以后的位置查找,如果目标项比列表中间项小,就在中间项以前的位置查找。
def fn(L,target): left = 0 right = len(L) - 1 while left <= right: mid = (left + right) // 2 if target == L[mid]: return mid elif target > L[mid]: left = mid + 1 else: right = mid - 1 return -1 L = [1,2,3,4,5,6,7,8,9] print(fn(L,9))
首先设置 while 循环的退出条件是:查找的目标项跟列表中的中间项相等。
为了实现这个退出条件,我们一分为二这个列表,看看目标项在列表前后的哪个部分,当第一遍循环之后我们缩小一半的查找区域,再次循环又缩小一半。直到匹配出目标项。
对于大小为 n 的列表,实际上执行了 n/2/2/2/2/ 的连续除法,直到结果为1,假设 k 是用 n 除以 2 的次数。要求解k,让 n/2^k=1 就行了,那么 n=2^k,k=㏒₂n ,因此二分查找的复杂度为 O(k=㏒₂n)。
结语
最近会放上一些算法的文章,来锻炼算法能力。毕竟最底层的东西才是最实用的。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Lodash 扩展JS通用方法
版权声明:本文首发 http://asing1elife.com ,转载请注明出处。 https://blog.csdn.net/asing1elife/article/details/82848345 Lodash是一个著名的javascript原生库,不需要引入其他第三方依赖。是一个意在提高开发者效率,提高JS原生方法性能的JS库 更多精彩 更多技术博客,请移步 asing1elife’s blog 官网 Lodash Documentation lodash 中文文档 语法 集合[Collection] _.find 在集合中获取到指定元素 var users = [ { 'user': 'barney', 'age': 36, 'active': true }, { 'user': 'fred', 'age': 40, 'active': false }, { 'user': 'pebbles', 'age': 1, 'active': true } ] // 自定义匹配规则 _.find(users, function(o) { return o.age < 40; }...
- 下一篇
重磅:JDK11正式发布!史上最全特性完整解读!
千呼万唤,JDK11 于 2018-09-25 正式发布!你是不是和笔者一样还在使用JDK8 呢?甚至有些开发者还在使用 JDK7!没关系,让我们先一睹 JDK11 的风采。 JDK11发布计划 2018/06/28 Rampdown Phase One (fork from main line) 2018/07/19 All Tests Run 2018/07/26 Rampdown Phase Two 2018/08/16 Initial Release Candidate 2018/08/30 Final Release Candidate 2018/09/25 General Availability 说明:GA即General Availability,也就是官方推荐可以广泛使用的版本。 JDK11特性一览 181: Nest-Based Access Control 309: Dynamic Class-File Constants 315: Improve Aarch64 Intrinsics 318: Epsilon: A No-Op Garbage Collector...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7安装Docker,走上虚拟化容器引擎之路
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Mario游戏-低调大师作品
- 2048小游戏-低调大师作品
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Thymeleaf,官方推荐html解决方案