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

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

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

    本文导语:  问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料...

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

我们先分析原问题:有一个大小为 n的数组A[0,1,2,…,n-1],求其中第k大的数。
我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可以确定该值,如果k=2,则扫描两边数组就可以确定第二大的数,依此类推下去,时间复杂度是O(k*n),如果k跟n是一个数量级,那么时间复杂度就是O(n*n)了,显然不是最优的解法。

考虑分治法,难点在于如何将该问题分解为两个子问题。
快速排序最基础的一步:
随机取某一个数x,将其与数组末尾元素交换,然后将比其小的数交换至前,比其大的数交换至后。
这一步使某一数组的快速排序问题分解成两个子数组的排序问题,现在我们就依此来解决取第k大的数这个问题。
设数组下表从0开始,至n-1结束。
1、 随机取某个数,将其与数组末尾元素交换。
a)        idx=rand(0,n-1);生成[0,n-1]间的随机数。
b)        Swap(array[idx], array[n-1]);
2、 用末尾元素x,将比x小的数交换至前,比x大的数交换至后,并返回此时x在数组中的位置mid。
3、 如果mid==n-k,那么返回该值,这就是第k大的数。
如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数。
如果mid

    
 
 

您可能感兴趣的文章:

  • 深入线性时间复杂度求数组中第K大数的方法详解
  • 将数组中指定数量的元素移动数组后面的实现代码
  • java中如何实现二维(多维)动态数组.谢谢
  • php通过数组实现多条件查询实现方法(字符串分割)
  • JSP的SESSION能存贮数组吗?我想实现“购物车”功能?
  • 如何实现给JavaBean赋值(要传给JavaBean的数值为数组)?
  • 怎样才能用java实现结构体数组,最好有代码!谢了!送上100分!!!!
  • php实现数组筛选奇数和偶数示例
  • C#的锯齿数组以及C++实现代码
  • 不使用php api函数实现数组的交换排序示例
  • ^v^~~~~求助:如何用javaBean实现在图象上增加文本,或把图象的像素存入数组。
  • java 重定义数组的实现方法(与VB的ReDim相像)
  • 如何实现将表单内容存进一个字符串数组变量?
  • java 二维数组矩阵乘法的实现方法
  • 使用递归实现数组求和示例分享
  • php实现把数组按指定的个数分隔
  • 急:请问如何实现函数中的数组返回?
  • php中多维数组按指定value排序的实现代码
  • php中使用array_filter()函数过滤空数组的实现代码
  • 如何实现动态二维数组?
  • php获取数组中重复数据的实现代码
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • C++ Strings(字符串) 成员 data():返回内容的字符数组形式
  • C++指针数组、数组指针、数组名及二维数组技巧汇总
  • C++ Strings(字符串) 成员 copy():将内容复制为一个字符数组
  • c#基础之数组与接口使用示例(遍历数组 二维数组)
  • C++ Strings(字符串) 成员 c_str():将字符串以C字符数组的形式返回
  • 如何将一个数组重新组成一个新的数组?
  • c++类对象数组初始化方式
  • php定义数组和使用示例(php数组的定义方法)
  • php数组函数之array_combine() 数组合并函数
  • 判断php数组维度(php数组长度)的方法
  • php数组函数之array_count_values() 统计数组中所有值出现的次数
  • 请问怎么对一个数组排序,数组的内容是字符串,可能是单个也可能是多个?
  • 在我的java程序中,我从数据库中得到一批数据,不能确定是多少个,我要把它保存到我的java数组中,可是怎样才能向C++中的数组一样可以自由分配空间,在java中我必需预先指定大小,不会一定要用java中的那个可改变数组大小的类吧?
  • 一个String类型的Vector向量数组如何转换成一个String类型数组(请给代码)?
  • php数组函数之array_unique() 去除数组中重复的元素值
  • C++中关于[]静态数组和new分配的动态数组的区别分析
  • php判断一个数组是否为另一个数组子集的方法
  • 将二维数组转为一维数组的2种方法
  • 文件描述符集fd_set * readfds;书上这样描述数组元素的每一位对应一个文件描述符,第一个元素代表文件描述符0到31,数组第二个元素代表文
  • 深入理解数组指针与指针数组的区别
  • php数组函数之array_key_exists() 查找数组键名是否存在


  • 站内导航:


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

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

    浙ICP备11055608号-3