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,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相关内容感兴趣的读者可查看本站专题:《Python数组操作技巧总结》、《Python字符串操作技巧汇总》、《Python函数使用技巧总结》、《Python入门与进阶经典教程》及《Python数据结构与算法教程》

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

时间: 2017-12-02

Python实现找出数组中第2大数字的方法示例

本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis

Python实现查找数组中任意第k大的数字算法示例

本文实例讲述了Python实现查找数组中任意第k大的数字算法.分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索.与快排不同的是,每次都减少了一半的排序. def partitionOfK(numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end

python中找出numpy array数组的最值及其索引方法

在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&

Python实现二维有序数组查找的方法

本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角

Python语言描述连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值

python求最大连续子数组的和

抛出问题: 求一数组如 l = [0, 1, 2, 3, -4, 5, -6],求该数组的最大连续子数组的和 如结果为[0,1,2,3,-4,5] 的和为7 问题分析: 这个问题很简单,直接暴力法,上代码. # -*- coding:utf-8 -*- # 日期:2018/6/9 7:46 # Author:小鼠标 # 最大连续子数组的和 l = [0, 1, 2, 3, -4, 5, -6] # 暴力求解 def violence(l = []): maxVal = 0 x,y=0,0 for

python求解数组中两个字符串的最小距离

题目: 给定一个数组 strs,其中的数据都是字符串,给定两个字符串 str1,str2.如果这两个字符串都在 strs数组中,就返回它们之间的最小距离:如果其中任何一个不在里面,则返回 -1:如果两个字符串相等,则返回 0. 例如:给定['*','3','*','5','10','9','7','1','*'],再给定两个字符串'* '和'9',通过函数求得返回值 3. 分析:有两种方法 方法1: 遍历数组 strs,分别记录两个 str1 和 str2 的位置.求得最小的一个距离数字.这样做

Python实现在某个数组中查找一个值的算法示例

第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机

JS 判断某变量是否为某数组中的一个值的3种方法(总结)

1.正则表达式 js 中判断某个元素是否存在于某个 js 数组中,相当于 PHP 语言中的 in_array 函数. Array.prototype.in_array=function(e){ var r=new RegExp(','+e+','); return (r.test(','+this.join(this.S)+','));}; 用法如下: var arr=new Array(['b',2,'a',4]); arr.in_array('b');//判断'b'字符是否存在于 arr 数

php 删除一维数组中某一个值元素的操作方法

1. 自己写for循环 从array里去掉$tmp这个元素的值 <?php $tmp = '324'; $arr = array( '0' => '321', '1' => '322', '2' => '323', '3' => '324', '4' => '325', '5' => '326', ); 代码 foreach( $arr as $k=>$v) { if($tmp == $v) unset($arr[$k]); } print_r($arr);

Python替换NumPy数组中大于某个值的所有元素实例

我有一个2D(二维) NumPy数组,并希望用255.0替换大于或等于阈值T的所有值.据我所知,最基础的方法是: shape = arr.shape result = np.zeros(shape) for x in range(0, shape[0]): for y in range(0, shape[1]): if arr[x, y] >= T: result[x, y] = 255 有更简洁和pythonic的方式来做到这一点吗? 有没有更快(可能不那么简洁和/或不那么pythonic)的

用python一行代码得到数组中某个元素的个数方法

想法由来 今天写代码过程中遇到一个需求,计算一个list中数值为1的元素的个数,其中这个list的元素数值不是为0就是为1. 一开始想到的是写个方法来计算: # 返回一个0,1数组中1的数量 def num_one(source_array): count = 0 for x in source_array: if x == 1: count += 1 return count 嗯好吧,然后觉得这是最low的方法了,就在想强大的python可不可以一行代码就做到以上的效果,然后发现真的可以. c

python [:3] 实现提取数组中的数

搜索答案搜索不到,自己试了一把. 首先生成一维数组 a =np.array([1,2,3,4,5,6,7,8,9]) >>> print a [1 2 3 4 5 6 7 8 9] 取数组前3个值 b =a[:3] >>> print b [1 2 3] 取前3个以后的值 b =a[3:] >>> print b [4 5 6 7 8 9] 取数组的后3个值 b =a[-3:] >>> print b [7 8 9] 取数组后3个以前

python输出数组中指定元素的所有索引示例

如下所示,代码为: array也可直接使用上面代码.测试如下: 以上这篇python输出数组中指定元素的所有索引示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

python 实现在无序数组中找到中位数方法

一.问题描述 1.求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置.要求:不能使用排序,时间复杂度尽量低 2.例如: lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5 lists = [3, 1, 2] , 中位数为 2 3.算法思想: 利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数

Python脚本如何在bilibili中查找弹幕发送者

总所周知bilibili是没有办法直接查看弹幕的发送者的,这使得当我们看到一些nt弹幕的时候虽然生气,却无可奈何,但是B站是可以屏蔽某个用户发送的弹幕的,这说明数据接口里肯定有用户信息,由于最近在学爬虫,所以我想先找找弹幕接口,分析下里面的数据. 找接口 找接口当然是随便打开一个视频然后F12啦,可是当我找了两圈后我傻眼了,没找到啊..得,不能把时间浪费在这种事情上,果断打开百度,不出所料,找到了如下的两个接口,都是XML格式网页 https://comment.bilibili.com/+ci