`

第(前)k大数问题

阅读更多

所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。

 

解法1我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn+k)

 

解法2利用选择排序或交互排序,K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)

 

解法3利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分SaSbSa中的元素大于等于XSb中元素小于X。这时有两种情况:

1.Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;

2.Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)

///////////

回忆一下快速排序,快排中的每一步,都是将待排数据分做两组,其中一组的数据的任何一个数都比另一组中的任何一个大,然后再对两组分别做类似的操作,然后继续下去……

在本问题中,假设N个数存储在数组S中,我们从数组S中随机找出一个元素X,把数组分为两部分SaSbSa中的元素大于等于XSb中元素小于X

这时,有两种可能性:

1.   Sa中元素的个数小于KSa中所有的数和Sb中最大的K-|Sa|个元素(|Sa|Sa中元素的个数)就是数组S中最大的K个数。

2.   Sa中元素的个数大于或等于K,则需要返回Sa中最大的K个元素。

这样递归下去,不断把问题分解成更小的问题,平均时间复杂度ON * log2K

 

解法4:二分[Smin,Smax]查找结果X,统计X在数组中出现,且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

 

解法5O(4*n)的方法对原数组建最大堆,然后popk即可。时间复杂度为O(4*n+k*logn)

 

解法6:维护一个k大小的最小堆,对于数组中的每一个元素判断与堆顶的大小,若堆顶较大,则不管,否则,弹出堆顶,将当前值插入到堆中。时间复杂度O(n*logk)

 

解法7利用hash保存数组中元素Si出现的次数,利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大数,平均情况下时间复杂度O(n)

//////////////

上面类快速排序的方法平均时间复杂度是线性的。能否有确定的线性算法呢?是否可以通过改进计数排序、基数排序等来得到一个更高效的算法呢?答案是肯定的。但算法的适用范围会受到一定的限制。

如果所有N个数都是正整数,且它们的取值范围不太大,可以考虑申请空间,记录每个整数出现的次数,然后再从大到小取最大的K个。比如,所有整数都在(0, MAXN)区间中的话,利用一个数组count[MAXN]来记录每个整数出现的个数(count[i]表示整数i在所有整数中出现的个数)。我们只需要扫描一遍就可以得到count数组。然后,寻找第K大的元素。

 

 

附注:

1.STL中可以用nth_element求得类似的第n大的数(由谓词决定),使用的是解法3中的思想,还可以用partial_sort对区间进行部分排序,得到类似前k大的数(由谓词决定),它采用的是解法5的思想。

2.求中位数实际上是第k大数的特例。

 

《编程之美》2.5节课后习题:

1.如果需要找出N个数中最大的K个不同的浮点数呢?比如,含有10个浮点数的数组(1.51.52.53.53.550-1.53.5)中最大的3个不同的浮点数是(53.52.5)。

解答:上面的解法均适用,需要注意的是浮点数比较时和整数不同,另外求hashkey的方法也会略有不同。

2.如果是找第k到第m0<k<=m<=n)大的数呢?

解答:如果把问题看做m-k+1个第k大问题,则前面解法均适用。但是对于类似前k大这样的问题,最好使用解法5或者解法7,总体复杂度较低。

3.在搜索引擎中,网络上的每个网页都有“权威性”权重,如pagerank。如果我们需要寻找权重最大的K个网页,而网页的权重会不断地更新,那么算法要如何变动以达到快速更新(incremental update)并及时返回权重最大的K个网页?

提示:堆排序?当每一个网页权重更新的时候,更新堆。还有更好的方法吗?

解答:要达到快速的更新,我们可以解法5,使用映射二分堆,可以使更新的操作达到O(logn)

4.在实际应用中,还有一个“精确度”的问题。我们可能并不需要返回严格意义上的最大的K个元素,在边界位置允许出现一些误差。当用户输入一个query的时候,对于每一个文档d来说,它跟这个query之间都有一个相关性衡量权重f(query,d)。搜索引擎需要返回给用户的就是相关性权重最大的K个网页。如果每页10个网页,用户不会关心第1000页开外搜索结果的“精确度”,稍有误差是可以接受的。比如我们可以返回相关性第10001大的网页,而不是第9999大的。在这种情况下,算法该如何改进才能更快更有效率呢?网页的数目可能大到一台机器无法容纳得下,这时怎么办呢?

提示:归并排序?如果每台机器都返回最相关的K个文档,那么所有机器上最相关K个文档的并集肯定包含全集中最相关的K个文档。由于边界情况并不需要非常精确,如果每台机器返回最好的K’个文档,那么K’应该如何取值,以达到我们返回最相关的90%*K个文档是完全精确的,或者最终返回的最相关的K个文档精确度超过90%(最相关的K个文档中90%以上在全集中相关性的确排在前K),或者最终返回的最相关的K个文档最差的相关性排序没有超出110%*K

解答:正如提示中所说,可以让每台机器返回最相关的K’个文档,然后利用归并排序的思想,得到所有文档中最相关的K个。最好的情况是这K个文档在所有机器中平均分布,这时每台机器只要K=K/nn为所有机器总数);最坏情况,所有最相关的K个文档只出现在其中的某一台机器上,这时K’需近似等于K了。我觉得比较好的做法可以在每台机器上维护一个堆,然后对堆顶元素实行归并排序。

5.如第4点所说,对于每个文档d,相对于不同的关键字q1,q2,,qm,分别有相关性权重fd,q1),fd,q2,,fd,qm)。如果用户输入关键字qi之后,我们已经获得了最相关的K个文档,而已知关键字qj跟关键字qi相似,文档跟这两个关键字的权重大小比较靠近,那么关键字qi的最相关的K个文档,对寻找qj最相关的K个文档有没有帮助呢?

解答:肯定是有帮助的。在搜索关键字qj最相关的K个文档时,可以在qj的“近义词”相关文档中搜索部分,然后在全局的所有文档中在搜索部分。

分享到:
评论

相关推荐

    区间k大数查询.zip

    在编程和算法领域,区间k大数查询是一个常见且具有挑战性的问题。通常,这个问题会涉及到以下知识点: 1. **排序算法**:解决此类问题的基础是能够快速对区间内的数进行排序,以便找出最大的k个数。常见的排序算法...

    深入第K大数问题以及算法概要的详解

    第K大数问题在计算机科学和算法设计中是一个常见的问题,涉及到如何在一组无序的数据中找到第k个最大的元素。这个问题在数据处理、数据库查询优化、数据分析等领域都有广泛的应用。下面将对几种不同的解法进行详细...

    典型的Top K算法 找出一个数组里面前K个最大数.doc

    Top K算法是解决一个经典的问题,即在一个大规模的数组中找到前K个最大数的问题。在这个问题中,我们需要在一个数组中找到前K个最大数,例如在搜索引擎中,需要找出最热门的10个查询串。下面我们将详细地介绍Top K...

    C++实现的O(n)复杂度内查找第K大数算法示例

    C++实现O(n)复杂度内查找第K大数算法示例 本文主要介绍了C++实现的O(n)复杂度内查找第K大数算法,通过实例形式分析了算法的原理以及具体实现方法。该算法可以在O(n)复杂度内查找第K大数,使得查找速度大大提高。 ...

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

    在编程和算法设计中,"数组中求第K大数"是一个常见的问题,它涉及到高效地从一组数据中找出第K个最大值。本问题的解决方案通常基于分治策略,如快速选择算法,这是一种简化版的快速排序算法,用于解决特定情况下的...

    D_(POJ_1723)(思维)(第k大数).cpp

    D_(POJ_1723)(思维)(第k大数).cpp

    大数除法问题

    ### 大数除法问题详解 #### 背景与挑战 在计算机科学与软件开发领域,处理大数运算是一项常见的需求。特别是在金融计算、密码学应用或是算法竞赛中,经常需要进行大数的加减乘除等操作。然而,由于整型变量(如`...

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

    线性时间复杂度求解数组中第K大数的问题是一个经典的数据结构与算法问题,它主要涉及到了排序算法中的快速选择算法。这篇文章将详细介绍如何在O(n)的时间复杂度内找到数组中的第K大数。 首先,理解这个问题的核心是...

    大数相乘代码及解析

    传统的乘法算法(如小学教的竖式乘法)在处理大数时效率较低,而且很容易遇到溢出问题。本文将深入分析一个使用字符数组实现的大数相乘算法,并通过具体的代码进行解释。 #### 二、问题背景与需求 在很多情况下,...

    大数相乘(矩阵方式)

    然而,Karatsuba算法的时间复杂度为O(n^log2(3)),约等于O(n^1.585),而Toom-Cook算法的时间复杂度更优,可以进一步降低到O(n^k),其中k小于2。这些算法通过分治策略将大问题拆解为小问题,然后进行组合,显著减少了...

    大数阶乘数据结构算法课程设计-副本.pdf

    动态数组也可以用来存储大数阶乘的累积结果,但是需要考虑数组的扩容问题。 二、数据的操作及其实现 在大数阶乘算法中,数据的操作包括累积运算和乘法运算。累积运算的特点是当前的计算结果是下次乘法运算的乘数。...

    ACM大数模版ACM大数模版

    在ACM(国际大学生程序设计竞赛)中,处理大数问题是非常常见的挑战,尤其是在涉及到算法设计和优化时。本文将详细讲解ACM大数模版中的三个主要操作:大数加法、大数减法和大数乘法。 **大数加法** 大数加法的实现...

    大数运算模板(C++)

    排列是指从n个元素中选择k个元素的所有可能的排列方式,而组合是指从n个元素中选择k个元素的所有可能的组合方式。 2. 大数存储:在该模板中,大数是使用数组来存储的,每个元素是一个int型的数字。数组的长度是MAX+1...

    大数相乘算法解析,实现20位的大数相乘

    5. **单个数字乘法**:在singleMulti函数中,我们将第一个大数与第二个大数的当前位相乘,得到一个中间结果。这个中间结果是小数形式,需要进行位移操作(乘以10的相应次幂)。 6. **错位相加**:在每次单个数字...

    大数计算器

    在IT领域,大数计算是一项重要的技术,尤其是在数学、密码学、金融计算和分布式系统中。这个名为"大数计算器"的项目是用C语言...理解并掌握大数计算的原理和C语言实现,对于提升编程技能和解决实际问题都有很大帮助。

Global site tag (gtag.js) - Google Analytics