Python实现查找数组中任意第k大的数字算法示例

本文实例讲述了Python实现查找数组中任意第k大的数字算法。分享给大家供大家参考,具体如下:

模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索。与快排不同的是,每次都减少了一半的排序。

def partitionOfK(numbers, start, end, k):
  if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
    return None
  low = start
  high = end
  key = numbers[start]
  while low < high:
    while low < high and numbers[high] >= key:
      high -= 1
    numbers[low] = numbers[high]
    while low < high and numbers[low] <= key:
      low += 1
    numbers[high] = numbers[low]
  numbers[low] = key
  if low < k:
    return partitionOfK(numbers, start + 1, end, k)
  elif low > k:
    return partitionOfK(numbers, start, end - 1, k)
  else:
    return numbers[low]
numbers = [3,5,6,7,2,-1,9,3]
print(sorted(numbers))
print(partitionOfK(numbers, 0, len(numbers) - 1, 5))

输出:返回了第五大排序的数字

[-1, 2, 3, 3, 5, 6, 7, 9]
6

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

时间: 2019-01-21

python3实现二叉树的遍历与递归算法解析(小结)

1.二叉树的三种遍历方式 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先中后指的是访问根节点的顺序 eg:先序 根左右 中序 左根右 后序 左右根 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历 a 先访问根节点 b 访问左节点 c 访问右节点 a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg 1.2 中序遍历 a 先访问左节点 b 访问根节点 c 访问右节点 ( ( ( h ) d ) b ( (

如何通过雪花算法用Python实现一个简单的发号器

实现一个简单的发号器 根据snowflake算法的原理实现一个简单的发号器,产生不重复.自增的id. 1.snowflake算法的简单描述 这里的snowflake算法是用二进制的,有64位.其中41位的时间戳表示:当前时间戳减去某个设定的起始时间,10位标识表示:不同的机器.数据库的标识ID等等,序列号为每秒或每毫秒内自增的id. 我做的时候没有用位运算去实现,而是做了一个十进制的,16位的(当时项目要求是16位的).但是实现发号器的基本策略是一样的,通过时间戳和标识来防止重复,通过序列号实现

Python实现简单层次聚类算法以及可视化

本文实例为大家分享了Python实现简单层次聚类算法,以及可视化,供大家参考,具体内容如下 基本的算法思路就是:把当前组间距离最小的两组合并成一组. 算法的差异在算法如何确定组件的距离,一般有最大距离,最小距离,平均距离,马氏距离等等. 代码如下: import numpy as np import data_helper np.random.seed(1) def get_raw_data(n): _data=np.random.rand(n,2) #生成数据的格式是n个(x,y) _grou

python TF-IDF算法实现文本关键词提取

TF(Term Frequency)词频,在文章中出现次数最多的词,然而文章中出现次数较多的词并不一定就是关键词,比如常见的对文章本身并没有多大意义的停用词.所以我们需要一个重要性调整系数来衡量一个词是不是常见词.该权重为IDF(Inverse Document Frequency)逆文档频率,它的大小与一个词的常见程度成反比.在我们得到词频(TF)和逆文档频率(IDF)以后,将两个值相乘,即可得到一个词的TF-IDF值,某个词对文章的重要性越高,其TF-IDF值就越大,所以排在最前面的几个词就

python实现鸢尾花三种聚类算法(K-means,AGNES,DBScan)

一.分散性聚类(kmeans) 算法流程: 1.选择聚类的个数k. 2.任意产生k个聚类,然后确定聚类中心,或者直接生成k个中心. 3.对每个点确定其聚类中心点. 4.再计算其聚类新中心. 5.重复以上步骤直到满足收敛要求.(通常就是确定的中心点不再改变. 优点: 1.是解决聚类问题的一种经典算法,简单.快速 2.对处理大数据集,该算法保持可伸缩性和高效率 3.当结果簇是密集的,它的效果较好 缺点 1.在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用 2.必须事先给出k(要生成的簇的数

Python实现在某个数组中查找一个值的算法示例

第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机

基于python的Paxos算法实现

理解一个算法最快,最深刻的做法,我觉着可能是自己手动实现,虽然项目中不用自己实现,有已经封装好的算法库,供我们调用,我觉着还是有必要自己亲自实践一下. 这里首先说明一下,python这种动态语言,对不熟悉的人可能看着比较别扭,不像java那样参数类型是固定的,所以看着会有些蛋疼.这里环境用的是python2.7. class Message: # command MSG_ACCEPTOR_AGREE = 0 # 追随者约定 MSG_ACCEPTOR_ACCEPT = 1 # 追随者接受 MSG_

基于python实现雪花算法过程详解

这篇文章主要介绍了基于python实现雪花算法过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Snowflake是Twitter提出来的一个算法,其目的是生成一个64bit的整数: 1bit:一般是符号位,不做处理 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年,到时候怎么办?要是这个系统能用69年,我相信这个系统早都重构了好多次了. 10bit:10bit用来记录机器ID

基于Python实现迪杰斯特拉和弗洛伊德算法

图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 2016年9月28日 @author: sx ''' b=999 G=[[0,1,5,b,b,b,b,b,b],\ [1,0,3,7,5,b,b,b,b],\ [5,3,0,b,1,7,b,b,b],\ [b,7,b,0,2,b,3,b,b],\ [b,5,1,2,0,3,6,9,b],\ [b,b,7,b,3,0,b,5

基于Python和Scikit-Learn的机器学习探索

你好,%用户名%! 我叫Alex,我在机器学习和网络图分析(主要是理论)有所涉猎.我同时在为一家俄罗斯移动运营商开发大数据产品.这是我第一次在网上写文章,不喜勿喷. 现在,很多人想开发高效的算法以及参加机器学习的竞赛.所以他们过来问我:"该如何开始?".一段时间以前,我在一个俄罗斯联邦政府的下属机构中领导了媒体和社交网络大数据分析工具的开发.我仍然有一些我团队使用过的文档,我乐意与你们分享.前提是读者已经有很好的数学和机器学习方面的知识(我的团队主要由MIPT(莫斯科物理与技术大学)和

基于python爬虫数据处理(详解)

一.首先理解下面几个函数 设置变量 length()函数 char_length() replace() 函数 max() 函数 1.1.设置变量 set @变量名=值 set @address='中国-山东省-聊城市-莘县'; select @address 1.2 .length()函数 char_length()函数区别 select length('a') ,char_length('a') ,length('中') ,char_length('中') 1.3. replace() 函数

基于Python实现文件大小输出

在数据库中存储时,使用 Bytes 更精确,可扩展性和灵活性都很高. 输出时,需要做一些适配. 1. 注意事项与测试代码 1.需要考虑 sizeInBytes 为 None 的场景. 2.除以 1024.0 而非 1024,避免丢失精度. 实现的函数为 getSizeInMb(sizeInBytes),通用的测试代码为 def getSizeInMb(sizeInBytes): return 0 def test(sizeInBytes): print '%s -> %s' % (sizeInB

基于python脚本实现软件的注册功能(机器码+注册码机制)

一.前言: 目的:完成已有python图像处理工具的注册功能 功能:用户运行程序后,通过文件自动检测认证状态,如果未经认证,就需要注册.注册过程是用户将程序运行后显示的机器码(C盘的卷序号)发回给管理员,管理员对机器码加密后生成加密文件或字符串返回给用户.每次启动程序,在有注册文件的情况下,程序就会通过DES和base64解码,并与此刻获取到的C盘卷序列号比对,如果一致则运行主程序.如果注册文件解码后与卷序号不一致,就要提醒用户输入注册码,如果对新输入的解码后和重新获取的机器码一致,则通过认证,

基于Python实现的ID3决策树功能示例

本文实例讲述了基于Python实现的ID3决策树功能.分享给大家供大家参考,具体如下: ID3算法是决策树的一种,它是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事.ID3算法,即Iterative Dichotomiser 3,迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法. 如下示例是一个判断海洋生物数据是否是鱼类而构建的基于ID3思想

基于python内置函数与匿名函数详解

内置函数 Built-in Functions abs() dict() help() min() setattr() all() dir() hex() next() slice() any() divmod() id() object() sorted() ascii() enumerate() input() oct() staticmethod() bin() eval() int() open() str() bool() exec() isinstance() pow() super

基于Python实现的微信好友数据分析

最近微信迎来了一次重要的更新,允许用户对"发现"页面进行定制.不知道从什么时候开始,微信朋友圈变得越来越复杂,当越来越多的人选择"仅展示最近三天的朋友圈",大概连微信官方都是一脸的无可奈何.逐步泛化的好友关系,让微信从熟人社交逐渐过渡到陌生人社交,而朋友圈里亦真亦幻的状态更新,仿佛在努力证明每一个个体的"有趣". 有人选择在朋友圈里记录生活的点滴,有人选择在朋友圈里展示观点的异同,可归根到底,人们无时无刻不在窥探着别人的生活,唯独怕别人过多地了解