Python实现返回数组中第i小元素的方法示例
作者：爱橙子的OK绷 发布时间：2021-12-23 14:58:44
标签：Python,数组,元素
本文实例讲述了Python实现返回数组中第i小元素的方法。分享给大家供大家参考，具体如下：
#! /usr/bin/env python
#coding=utf-8
#期望为线性时间的选择算法
import random
class RandomSelect(object):
def Partition(self,a, p, r):
x=a[r]
i=p-1
for j in range(p, r):
'''如果a[j]>x,则只需将j的值加1即可使循环不变量继续保持;
如果a[j]<=x,则将下标i的值加1，并交换a[i]和a[j],再将
j的值加1.此时循环不变量同样得到保持'''
if a[j]<=x:
i=i+1
a[i], a[j]=a[j], a[i]
a[i+1], a[r]=a[r], a[i+1]
return i+1
def RandomPartition(self,a, p, r):
i=random.randint(p, r) #生成的随机数为p=<i<=r
a[r], a[i]=a[i], a[r]
return self.Partition(a, p, r)
def randomSelect(self,a,p,r,i):
if p==r:
return a[p]
q=self.RandomPartition(a,p,r)
k=q-p+1
if i==k:
return a[q]
elif i<k:
return self.randomSelect(a,p,q-1,i)
else:
return self.randomSelect(a,q+1,r,i-k)
if __name__ == '__main__':
print "脚本之家测试结果："
a=[random.randint(0,20) for i in range(10)]
print a
#a=sorted(a)
#print a
r=RandomSelect()
r.randomSelect(a,0,len(a)-1,3)
print a[2]#数组中的第三小的数
a=sorted(a)
print a
运行结果：
希望本文所述对大家Python程序设计有所帮助。
来源：http://blog.csdn.net/will130/article/details/45244649
0
投稿猜你喜欢
面对不断成长的用户，跟随用户的脚步齐步向前，做引起共鸣的改变，去除低龄化的设计，用成熟稳重的心态面对用户。QQBanner自2006 年推出- 而Easp类中提供了大量实用的ASP通用过程及方法，可以简化大部分的ASP操作。目前只提供了VBScript版，JScript版将来可能会提
- 在我的前一篇教程《九宫格基本布局》中，我介绍了用相对定位加绝对定位的方法来制作九宫格的基本布局。这是一种比较符合人们惯性思维的方法，好像制作
- 本文实例讲述了Laravel框架文件上传功能实现方法。分享给大家供大家参考，具体如下：以Laravel 5.2.45 框架为主，进行文件上传
- SQL Server所谓的分布式查询（Distributed Query）是能够访问存放在同一部计算机或不同计算机上的SQL Server或
- 何为质数: 只能被1 和 自身 整除的数;方法: 利用js中求模, 看是否有余数. ---> 3％2 = 1; 5％2 = 3....
- 五花八门的SQL产品多得要命，或许你早顾不得其它甩开袖子就动手干了。但你要同时采用ASP和SQL的话就可能会头晕。MySQL、SQL Ser
- 准确地讲，Python没有专门处理字节的数据类型。但由于str既是字符串，又可以表示字节，所以，字节数组＝str。而在C语言中，我们可以很方
- andot提出问题：在做 ajax 编程时，我们常常需要将 xmlhttp 获取到的页面内容通过 innerHTML 来赋给某个容器（比如
- 想必每个DBA都喜欢挑战数据导入时间，用时越短工作效率越高，也充分的能够证明自己的实力。实际工作中有时候需要把大量数据导入数据库，然后用于各
- 1.在使用MySQL和php的时候出现过中文乱码问题(1) 只要是gb2312,gbk,utf8等支持多字节编码的字符集都可以储存汉字，当然
- 各位想必都知道，onfocus="this.blur()"这条代码能消除链接时的虚线框，但你有没有想过，如果你的网页上有
- 很多人在使用AJAX调用别人站点内容的时候,JS会提示"没有权限"错误，这是XMLHTTP组件的限制-安全起见禁止访问非
- CSS的学习和其他的学习一样,都需要特定的方法才能比较快的去掌握它.要想掌握CSS, 首先要学会HTML，我刚开始是从零开始学习的
- asp之家注：学习asp网页编程的朋友一定用过ACCESS数据库，access的简单方便，大大降低了asp初学者学习asp的门槛，对于学习a
- 这个程序将记数器的数字放在ACCESS数据库中,当然你也能用你希望其它的ODBC数据源.这个程序从URL中读取记数信息.如下:< IM
- 本文实例为大家分享了React实现表格选取的具体代码，供大家参考，具体内容如下在工作中，遇到一个需求，在表格中实现类似于Excel选中一片区
- 我们经常见到很多网站留言系统的显示访客的IP地址都是隐藏了一部分，以达到隐蔽访客真实地理位置的功能。如：111.222.333.*，当然在系
- 之前在《首都机场的点烟器》中分析了一个软件系统所处的状态并且列举了不同的状态所需要的展示给用户的各类信息，我们先简单回顾一下：要设计一个软件
- Python中有哪几种方法安装第三方模块，安装Python第三方模块的方法有很多，这里介绍三种方法安装第三方模块。【方法一】: 通过setu
