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

yipeiwu_com6年前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 "【听图阁-专注于Python设计】测试结果:"
  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数组操作技巧总结》、《Python字符串操作技巧汇总》、《Python函数使用技巧总结》、《Python入门与进阶经典教程》及《Python数据结构与算法教程

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

相关文章

numpy中的高维数组转置实例

numpy中的高维数组转置实例

numpy中的ndarray很适合数组运算 transpose是用来转置的一个函数,很容易让人困惑,其实它是对矩阵索引顺序的一次调整。原先矩阵是一个三维矩阵,索引顺序是x,y,z,角标...

Python 快速实现CLI 应用程序的脚手架

Python 快速实现CLI 应用程序的脚手架

今天跟大家分享一下如何快速实现一个Python CLI应用程序的脚手架,之所以会做这个是因为当时需要做一个运维的小工具希望用命令行的方式来使用,但是搜遍网上很多资料都没有系统讲解从开发、...

Python实现12306火车票抢票系统

Python实现12306火车票抢票系统

Python实现12306火车票抢票系统效果图如下所示: 具体代码如下所示: import urllib.request as request import http.coo...

Python保存MongoDB上的文件到本地的方法

本文实例讲述了Python保存MongoDB上的文件到本地的方法。分享给大家供大家参考,具体如下: MongoDB上的文档通过GridFS来操作,Python也可以通过pymongo连接...

TensorFlow绘制loss/accuracy曲线的实例

TensorFlow绘制loss/accuracy曲线的实例

1. 多曲线 1.1 使用pyplot方式 import numpy as np import matplotlib.pyplot as plt x = np.arange(1,...