频道栏目
首页 > 程序开发 > Web开发 > Python > 正文
Python如何实现返回数组中第i小元素的方法教程
2018-01-03 14:16:44      个评论      
收藏   我要投稿
本文实例讲述了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=

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

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编程如何实现二分法及牛顿迭代法求平方根代码
下一篇:Python内置函数:vars的详细使用方法
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站