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:
    return None
  low = start
  high = end
  key = numbers[start]
  while low < high:
    while low < high and numbers[high] >= key:
      high -= 1
    numbers[low] = numbers[high]
    while low < high and numbers[low] <= key:
      low += 1
    numbers[high] = numbers[low]
  numbers[low] = key
  if low < k:
    return partitionOfK(numbers, start + 1, end, k)
  elif low > k:
    return partitionOfK(numbers, start, end - 1, k)
  else:
    return numbers[low]
numbers = [3,5,6,7,2,-1,9,3]
print(sorted(numbers))
print(partitionOfK(numbers, 0, len(numbers) - 1, 5))

输出：返回了第五大排序的数字

[-1, 2, 3, 3, 5, 6, 7, 9]
6

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

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

赞 (0)

相关推荐

  • 基于python的Paxos算法实现

    基于python的Paxos算法实现

    理解一个算法最快,最深刻的做法,我觉着可能是自己手动实现,虽然项目中不用自己实现,有已经封装好的算法库,供我们调用,我觉着还是有必要自己亲自实践一下. 这里首先说明一下,python这种动态语言,对不熟悉的人可能看着比较别扭,不像java那样参数类型是固定的,所以看着会有些蛋疼.这里环境用的是python2.7. class Message: # command MSG_ACCEPTOR_AGREE = 0 # 追随者约定 MSG_ACCEPTOR_ACCEPT = 1 # 追随者接受 MSG_

  • 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()) #随机

  • Python实现简单层次聚类算法以及可视化

    本文实例为大家分享了Python实现简单层次聚类算法,以及可视化,供大家参考,具体内容如下 基本的算法思路就是:把当前组间距离最小的两组合并成一组. 算法的差异在算法如何确定组件的距离,一般有最大距离,最小距离,平均距离,马氏距离等等. 代码如下: import numpy as np import data_helper np.random.seed(1) def get_raw_data(n): _data=np.random.rand(n,2) #生成数据的格式是n个(x,y) _grou

  • python3实现二叉树的遍历与递归算法解析(小结)

    1.二叉树的三种遍历方式 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先中后指的是访问根节点的顺序 eg:先序 根左右 中序 左根右 后序 左右根 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历 a 先访问根节点 b 访问左节点 c 访问右节点 a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg 1.2 中序遍历 a 先访问左节点 b 访问根节点 c 访问右节点 ( ( ( h ) d ) b ( (

  • python TF-IDF算法实现文本关键词提取

    TF(Term Frequency)词频,在文章中出现次数最多的词,然而文章中出现次数较多的词并不一定就是关键词,比如常见的对文章本身并没有多大意义的停用词.所以我们需要一个重要性调整系数来衡量一个词是不是常见词.该权重为IDF(Inverse Document Frequency)逆文档频率,它的大小与一个词的常见程度成反比.在我们得到词频(TF)和逆文档频率(IDF)以后,将两个值相乘,即可得到一个词的TF-IDF值,某个词对文章的重要性越高,其TF-IDF值就越大,所以排在最前面的几个词就

  • 如何通过雪花算法用Python实现一个简单的发号器

    实现一个简单的发号器 根据snowflake算法的原理实现一个简单的发号器,产生不重复.自增的id. 1.snowflake算法的简单描述 这里的snowflake算法是用二进制的,有64位.其中41位的时间戳表示:当前时间戳减去某个设定的起始时间,10位标识表示:不同的机器.数据库的标识ID等等,序列号为每秒或每毫秒内自增的id. 我做的时候没有用位运算去实现,而是做了一个十进制的,16位的(当时项目要求是16位的).但是实现发号器的基本策略是一样的,通过时间戳和标识来防止重复,通过序列号实现

  • python实现鸢尾花三种聚类算法（K-means,AGNES,DBScan）

    一.分散性聚类(kmeans) 算法流程: 1.选择聚类的个数k. 2.任意产生k个聚类,然后确定聚类中心,或者直接生成k个中心. 3.对每个点确定其聚类中心点. 4.再计算其聚类新中心. 5.重复以上步骤直到满足收敛要求.(通常就是确定的中心点不再改变. 优点: 1.是解决聚类问题的一种经典算法,简单.快速 2.对处理大数据集,该算法保持可伸缩性和高效率 3.当结果簇是密集的,它的效果较好 缺点 1.在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用 2.必须事先给出k(要生成的簇的数

  • 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实现查找二叉搜索树第k大的节点功能示例

    Python实现查找二叉搜索树第k大的节点功能示例

    本文实例讲述了Python实现查找二叉搜索树第k大的节点功能.分享给大家供大家参考,具体如下: 题目描述 给定一个二叉搜索树,找出其中第k大的节点 就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减一就行. 代码1 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def __init__(self): self.k = 0 de

  • PHP查找数组中只出现一次的数字实现方法【查找特定元素】

    本文实例讲述了PHP查找数组中只出现一次的数字实现方法.分享给大家供大家参考,具体如下: 问题: 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,b],其中ab是出现一次的两个数字 $count = array_count_values($array); foreach

  • Python查找数组中数值和下标相等的元素示例【二分查找】

    本文实例讲述了Python查找数组中数值和下标相等的元素.分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的.请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组[-3,-1,1,3,5]中,3和他的下标相等. 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标.如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找. 算法示例: # -*-

  • 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,则

  • 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)的

  • 利用js查找数组中指定元素并返回该元素的所有索引示例

    前言 这篇文章主要给大家介绍的是利用js查找数组中指定元素并返回该元素的所有索引的相关资料,文中给出了详细的示例代码,下面话不多说,来看看详细的代码示例吧. 示例代码 //在数组中查找所有出现的x,并返回一个包含匹配索引的数组 function findall(a,x){ var results=[], len=a.length, pos=0; while(pos<len){ pos=a.indexOf(x,pos); if(pos===-1){//未找到就退出循环完成搜索 break; } r

  • 数组中求第K大数的实现方法

    问题:有一个大小为n的数组A[0,1,2,-,n-1],求其中第k大的数.该问题是一个经典的问题,在<算法导论>中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表.该问题还可以变形为:有一个大小为 n的数组A[0,1,2,-,n-1],求其中前k大的数.一字之差,原问题是"第k大",变形的问题是"前k大",但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇. 我们先分

  • JS查找数组中重复元素的方法详解

    JS查找数组中重复元素的方法详解

    本文实例讲述了JS查找数组中重复元素的方法.分享给大家供大家参考,具体如下: JS的数据类型有一个数组.今天我们就来谈谈对数组的一种处理.相信很多人都遇到过从数组中查找出不重复的元素,但是我遇到的却是从数组中查找出重复的元素. 从js数组中查找出不重复的元素的方法有很多,下面就给大家列举一个: <!DOCTYPE html> <html> <body> <script> Array.prototype.deleteEle=function(){ var ne

  • php数组函数序列之in_array() - 查找数组中是否存在指定值

    in_array()定义和用法 in_array() 函数查找数组中是否存在指定值. 语法 in_array(value,array,type)参数 描述 value 必需.规定要在数组搜索的值. array 必需.规定要搜索的数组. type 可选.如果设置该参数为 true,则检查搜索的数据与数组的值的类型是否相同. 说明 如果给定的值 value 存在于数组 array 中则返回 true.如果第三个参数设置为 true,函数只有在元素存在于数组中且数据类型与给定值相同时才返回 true.

随机推荐