当前位置:  编程技术>c/c++/嵌入式

深入线性时间复杂度求数组中第K大数的方法详解

    来源: 互联网  发布时间:2014-10-14

    本文导语:  求数组中第K大的数可以基于快排序思想,步骤如下:1、随机选择一个支点2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)3、设左部分的长度为L,当K < L时,递归地在左部分找...

求数组中第K大的数可以基于快排序思想,步骤如下:
1、随机选择一个支点
2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)
3、设左部分的长度为L,
当K < L时,递归地在左部分找第K大的数
当K > L时,递归地在有部分中找第(K - L)大的数
当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数
以上思想的代码实现如下:
代码如下:

/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei
** data   :2011-08-07 
**/
#include "iostream"
using namespace std;
//基于快速排序思想,求数组a中第k大的数,low和high分别为数组的起始和结束位置
//时间复杂度为o(n),n为数组的长度
//1

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 深入理解数组指针与指针数组的区别
  • 深入反射生成数组的详解
  • 数组重排序(如何将所有奇数都放在所有偶数前面)的深入分析
  • 数组和指针的区别深入剖析
  • 数组指针、指针数组以及二位数组的深入解析
  • 通过实例深入理解linux shell数组
  • linux shell数组深入学习理解
  • 深入解析C++中的指针数组与指向指针的指针
  • 深入理解c语言数组
  • Docker支持更深入的容器日志分析
  • 关于《深入浅出MFC》
  • Linux有没有什么好的高级的书,我要深入,
  • 深入理解linux内核
  • [100分]有没有关于binutils的深入的资料?或者深入底层的资料?
  • 深入理解PHP内核 TIPI
  • 想深入学习Java应该学习哪些东西
  • 哪位有《JSP深入编程》电子版?
  • 想要深入学习LINUX该学什么?
  • 100分求:哪儿有《深入理解linux内核》可供下哉!
  • 如何深入Linux的内核学习?
  • U-BOOT得掌握到什么程序,用不用深入去学
  • 想深入了解操作系统该怎么做
  • 前一阵子学习了shell脚本,如果想深入点了解linux可以看什么书呢
  • 问一个《深入理解计算机系统》中的问题
  • 深入多线程之:深入分析Interlocked
  • ##想买书深入学习linux下的编程,请指教
  • 深入JDBC sqlserver连接写法的详解
  • 深入oracle特定信息排序的分析
  • 深入分析C中不安全的sprintf与strcpy
  • 哪儿有下载《深入理解Linux内核》这本书?(中文)




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3