Python实现返回数组中第i小元素的方法示例 -清零世界

概述

本文实例讲述了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小元素的方法示例所遇到的程序开发问题。

如果您也喜欢它,动动您的小指点个赞吧

Python实现返回数组中第i小元素的方法示例

概述

总结

分类汇总

您的鼓励是对我最大的支持