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

yipeiwu_com5年前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程序设计有所帮助。

相关文章

python pytest进阶之xunit fixture详解

前言 今天我们再说一下pytest框架和unittest框架相同的fixture的使用, 了解unittest的同学应该知道我们在初始化环境和销毁工作时,unittest使用的是set...

python Opencv将图片转为字符画

python Opencv将图片转为字符画

做了个Python的小练习,网上有人是利用PIL中的Image来实现的,觉得Opencv库挺方便的,于是利用Opencv库来实现了一下,代码如下: # -*- coding: utf...

pybind11和numpy进行交互的方法

使用一个遵循buffer protocol的对象就可以和numpy交互了. 这个buffer_protocol要有哪些东西呢? 要有如下接口: struct buffer_i...

余弦相似性计算及python代码实现过程解析

余弦相似性计算及python代码实现过程解析

A:西米喜欢健身 B:超超不爱健身,喜欢打游戏 step1:分词 A:西米/喜欢/健身 B:超超/不/喜欢/健身,喜欢/打/游戏 step2:列出两个句子的并集 西米/喜欢/健身/超...

Python面向对象基础入门之设置对象属性

前言 前面我们已经介绍了 python面向对象入门教程之从代码复用开始(一) ,这篇文章主要介绍的是关于Python面向对象之设置对象属性的相关内容,下面话不多说了,来一起看看...