概述
本文实例讲述了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,r): i=random.randint(p,r) #生成的随机数为p=<i<=r a[r],a[i]=a[i],a[r] return self.Partition(a,r) def randomSelect(self,r,i): if p==r: return a[p] q=self.RandomPartition(a,r) k=q-p+1 if i==k: return a[q] elif i<k: return self.randomSelect(a,q-1,i) else: return self.randomSelect(a,q+1,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,len(a)-1,3) print a[2]#数组中的第三小的数 a=sorted(a) print a
运行结果:
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数组操作技巧总结》、《Python字符串操作技巧汇总》、《Python函数使用技巧总结》、《Python入门与进阶经典教程》及《Python数据结构与算法教程》
希望本文所述对大家Python程序设计有所帮助。
总结
以上是编程之家为你收集整理的Python实现返回数组中第i小元素的方法示例全部内容,希望文章能够帮你解决Python实现返回数组中第i小元素的方法示例所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧