Python实现返回数组中第i小元素的方法示例
作者：爱橙子的OK绷 发布时间：2021-12-23 14:58:44
标签：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 "脚本之家测试结果："
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程序设计有所帮助。
来源：http://blog.csdn.net/will130/article/details/45244649
0
投稿猜你喜欢
- 网页布局中常有的一种情况就是网页主体部分分成一行两列；而在很多种情况下，设计师们常把左右两列的背景色设计成不同色彩，以实现内容块的明显区分；
我们用pycharm写CSS的时候，是不是苦于没有提示，那么pycharm中如何显示CSS提示呢？下面小编给大家分享一下。首先点击左上角的f- 使用非对称加密主要是借助openssl的公钥和私钥，用公钥加密私钥解密，或者私钥加密公钥解密。1.安装openssl和php的openssl
- 问题：生产环境的数据库可能比较大，如果直接进行全备而不压缩的话，备份集就会占用了大量磁盘空间。给备份文件的存放管理带来不便。解决方案：通过w
- 此BUG最初是在《前端观察》网站刊登，这里再描述一下，代码如下：<style>*{ padding:0; m
- 本文实例讲述了Python爬虫PyQuery库基本用法。分享给大家供大家参考，具体如下：PyQuery库也是一个非常强大又灵活的网页解析库，
- 这是lgzx公司的一道面试题，要求给js的String添加一个方法，去除字符串两旁的空白字符（包括空格、制表符、换页符等）。 String.
- count()方法返回obj出现在列表的次数。语法以下是count()方法的语法：list.count(obj)参数
- 什么是 Python？自20世纪90年代初Python语言诞生至今，它已被逐渐广泛应用，Python 已然成为最受欢迎的程序设计语言之一，特
- 前言在学习Flask框架的蓝图时，遇到导包时用到了`from . 模块 import 对象`，然后试了试直接 import会报错，直接告诉我
- 本文实例讲述了js控制输入框获得和失去焦点时状态显示的方法。分享给大家供大家参考。具体实现方法如下：<!DOCTYPE html PU
- 本文实例为大家分享了bootstrapValidator表单验证的具体代码，供大家参考，具体内容如下1.页面引入css、js<link
- 本文实例为大家分享了python实现购物车功能的具体代码，供大家参考，具体内容如下功能要求：要求用户输入总资产，例如：2000显示商品列表，
- 当使用vue做登录的时候，我们会把拿到的部分用户信息存在vuex+cookie中，我们知道，vuex的数据是会随着浏览器刷新而丢失的，此时我
- 前言在面向对象的编程范式中，封装都是必不可少的一个概念，而在诸如 Java，C++等传统的面向对象的语言中， 私有成员是实现封装的一个重要途
- 概述在我们使用内置打印函数print时，打印出的Python数据结构对象总是一行的输出的方式，这样对数据结构较复杂或数据较多的对象的显示并不
- random 模块中的常用函数random()返回一个位于区间 [0,1] 内的实数；uniform(a, b)返回一个位于区间 [a,b]
- 问题背景在项目开发过程中，我遇到一个需求：对于某条记录，一个用户对它进行操作时会持续比较久，希望在一个用户的操作期间，不允许有另一个用户操作
- 最近公司在研发app,选择了基于Vue框架的vux组件库，现总结在实现上拉刷新功能遇到的坑：1.问题：只刷新一次，解决方法：需要自己手动重置
- 1.数据的容量：1-3年内会大概多少条数据，每条数据大概多少字节； 2.数据项：是否有大字段，那些字段的值是否经常被更新； 3.数据查询SQ
