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

相关文章

Python对两个有序列表进行合并和排序的例子

假设有2个有序列表l1、l2,如何效率比较高的将2个list合并并保持有序状态,这里默认排序是正序。 思路是比较简单的,无非是依次比较l1和l2头部第一个元素,将比较小的放在一个新的列表...

通过 Django Pagination 实现简单分页功能

通过 Django Pagination 实现简单分页功能

作者:HelloGitHub-追梦人物 文中所涉及的示例代码,已同步更新到 HelloGitHub-Team 仓库 当博客上发布的文章越来越多时,通常需要进行分页显示,以免所有的文章都...

Python3.6简单反射操作示例

Python3.6简单反射操作示例

本文实例讲述了Python3.6简单反射操作。分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #!python3 # ----------------...

Python实现基于C/S架构的聊天室功能详解

Python实现基于C/S架构的聊天室功能详解

本文实例讲述了Python实现基于C/S架构的聊天室功能。分享给大家供大家参考,具体如下: 一、课程介绍 1.简介 本次项目课是实现简单聊天室程序的服务器端和客户端。 2.知识点 服务器...

PYTHON 中使用 GLOBAL引发的一系列问题

哪里出问题了   python 中,使用 global 会将全局变量设为本函数可用。同时,在函数内部访问变量会先本地再全局。   在嵌套函数中,使用 global 会产生不合常理的行为。...