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

yipeiwu_com5年前Python基础

本文实例讲述了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程序设计有所帮助。

相关文章

Linux 修改Python命令的方法示例

Linux 修改Python命令的方法示例

Linux默认python命令指向的是/usr/bin下的python,这个python指向同目录下python2,以及pip默认也是python2的pip,想修改成pip指向pip3,...

python使用循环实现批量创建文件夹示例

代码很简单,其中用到了python的sys模块,大家参考使用吧复制代码 代码如下:import os,sysbase = 'C:/'i = 1for j in range(100):&n...

windows10下python3.5 pip3安装图文教程

windows10下python3.5 pip3安装图文教程

最近Google官方的开发者博客中宣布新的版本Tensorflow(0.12)将增加对Windows的支持,想试着windows10下学习tensorflow,之前已经安装anacond...

在Django中创建第一个静态视图

正如我们的第一个目标,创建一个网页,用来输出这个著名的示例信息: Hello world. 如果你曾经发布过Hello world页面,但是没有使用网页框架,只是简单的在h...

python对绑定事件的鼠标、按键的判断实例

当多个事件绑定了同一个命令,那么在命令内部根据不同的事件进行处理的时候,怎么确定哪个事件发生了呢,用下面的来检测,经过测试处理tab键和alt键不能识别,其他单个都能被识别。 还有个事件...