寻找第K元素的八大算法、源码及拓展

一、问题描述 

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

第K大问题可以是现实问题,譬如竞价排名中的第K个排名,或者多个出价者中的第K大价格等等。


二、解法归纳

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

很好理解,利用快排对所有元素进行排序,然后找到第K个元素即可。

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

也是初级解法,且很鸡肋。快排只有第一次时间复杂度较高,后面每次查询时间复杂度均为常数。而选择排序不论是排序还是查询,时间复杂度都很高。

解法3: 利用快速排序的思想,从数组S中随机找出一个元素dX,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。时间复杂度可以达到近似O(n)

这时有两种情况:

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

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

3.递归以上两步直到找到为止。

解法4:对原数组建最大堆,然后pop出k次即可。时间复杂度为O(n+ k*logn)

这其实也是个排序算法。

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

这个算法的最大优势在于,如果数组非常非常大的话,利用普通的排序是爆内存的。用它的话,则只用到K的内存。

解法6:解法4的优化版解法,建堆后不完全重建

与上述思路4类似,不同的是在对元素数组原地建最大堆O(n)后,然后提取K次,但是每次提取时,换到顶部的元素只需要下移顶多k次就足够了,下移次数逐次减少(而上述思路7每次提取都需要logn,所以提取k次,思路7需要k*logn。而本思路8只需要K^2)。此种方法的复杂度为O(n+k^2)。每次提取K后,换到顶部的元素需要下移的最大次数越少,保证了最坏情况下的效率。

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

解法8:来自圣经的算法,BFPRT算法。又名五划分中项的中项法。采用了与解法3相似的解法,但是由于高超的选择了枢纽元素,在最坏情况下亦能做到O(N)的复杂度。

下面是算法主要步骤:

     其中有些细节的处理,主要是边界问题还是比较关键,后面会给出这些问题。

     数据有n个,取出最小的k个数字

     终止条件:n=1时,返回的即是i小元素。

     算法步骤:

     step1:将n个元素每5个一组,分成n/5(上界)组,最后的一个组的元素个数为n%5,有效的组数为n/5。

     step2:取出每一组的中位数,最后一个组的不用计算中位数,任意排序方法,这里的数据比较少只有5个,

                  可以用简单的冒泡排序或是插入排序。

     step3: 将各组的中位数与数组开头的数据在组的顺序依次交换,这样各个组的中位数都排在了数据的左边。

                  递归的调用中位数选择算法查找上一步中所有组的中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

     step4: 按照x划分,大于或者等于x的在右边,小于x的在左边,关于setp4数据的划分,中位数放在左边或是右边会有些影响。

                  后面的代码调试将会看到。

     step5:step4中划分后数据后返回一个下表i,i左边的元素均是小于x,i右边的元素包括i都是大于或是等于x的。

                  若i==k,返回x;

                  若i<k,在小于x的元素中递归查找第i小的元素;

                  若i>k,在大于等于x的元素中递归查找第i-k小的元素。

我在github上贴出了代码实现:点击查看


三、中位数问题

中位数问题其实是第K大问题的一个自问题。可以用所有第K大问题的算法来解答。我们在这里提出几个更加严格的中位数问题。

1.动态中位数查找。实现在对数时间内插入元素,常数时间内找到中位数,对数时间内删除中位数。

我们假定在集合中有偶数个元素时,中位数是指较小的那个中间数。用两个堆,一个大顶堆包含集合里较小的(N+1)/2个数,另一个小顶堆包含集合里较大的另一半数。查询中位数时,直接看大顶堆的堆顶元素即可。插入元素时,先将其与两个堆顶元素比较,以决定插入哪个堆。如果插入之后两堆的元素个数之差超过了1,就把多的那个堆的堆顶元素插入到另一堆里。删除元素时,将中位数删掉之后,同样调整两个堆的元素个数。

在GitHub上找到了别人的一个实现:点击查看

2.求两个有序数组的中位数。

这又是一个变体,可以扩展为求两个有序数组的第K位数。最简单的思路当然是合并数组,然后再直接求有序数组的第K位数,这是一个O(n)的解法。然而,对于“Kth element in 2 sorted array”一类问题来说, 如下图,两个中位数 A[m/2] 和 B[n/2], 可以将数组划分为四个部分。而丢弃哪一个部分取决于两个条件:1, (m/2 + n/2)?k;2,A[m/2] ? B[n/2];

如果 (m/2 + n/2) > k,那么意味着,当前中位数取高了,正确的中位数要么在 Section 1或者Section3中。如果A[m/2] > B[n/2], 意味着中位数肯定不可能在Section 2里面,那么新的搜索可以丢弃这个区间段了。同理可以推断出余下三种情况,如下所示:

If (m/2+n/2+1) > k && am/2 > bn/2 , drop Section 2
If (m/2+n/2+1) > k && am/2 < bn/2 , drop Section 4
If (m/2+n/2+1) < k && am/2 > bn/2 ,  drop Section 3
If (m/2+n/2+1) < k && am/2 < bn/2 ,  drop Section 1

简单的说,就是或者丢弃最大中位数的右区间,或者丢弃最小中位数的左区间。

附上代码如下:

double findMedianSortedArrays(int A[], int m, int B[], int n) {  
2:      if((n+m)%2 ==0)  
3:      {  
4:        return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;  
5:      }  
6:      else  
7:        return GetMedian(A,m,B,n, (m+n)/2+1);        
8:    }  
9:       int GetMedian(int a[], int n, int b[], int m, int k)  
10:       {  
11:            assert(a && b);   
12:            if (n <= 0) return b[k-1];  
13:            if (m <= 0) return a[k-1];  
14:            if (k <= 1) return min(a[0], b[0]);   
15:            if (b[m/2] >= a[n/2])  
16:            {  
17:                 if ((n/2 + 1 + m/2) >= k)  
18:                      return GetMedian(a, n, b, m/2, k);  
19:                 else  
20:                      return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1));  
21:            }  
22:            else  
23:            {  
24:                 if ((m/2 + 1 + n/2) >= k)  
25:                      return GetMedian( a, n/2,b, m, k);  
26:                 else  
27:                      return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));  
28:            }  
29:       } 

四、一些扩展( 《编程之美》2.5节课后习题):

1. 如果需要找出N个数中最大的K个不同的浮点数呢?比如,含有10个浮点数的数组(1.5,1.5,2.5,3.5,3.5,5,0,- 1.5,3.5)中最大的3个不同的浮点数是(5,3.5,2.5)。     解答:上面的解法均适用,需要注意的是浮点数比较时和整数不同,另外求hashkey的方法也会略有不同。

2. 如果是找第k到第m(0<k<=m<=n)大的数呢?     解答:如果把问题看做m-k+1个第k大问题,则前面解法均适用。但是对于类似前k大这样的问题,最好使用解法5或者解法7,总体复杂度较低。

3. 在搜索引擎中,网络上的每个网页都有“权威性”权重,如page rank。如果我们需要寻找权重最大的K个网页,而网页的权重会不断地更新,那么算法要如何变动以达到快速更新(incremental update)并及时返回权重最大的K个网页?     提示:堆排序?当每一个网页权重更新的时候,更新堆。还有更好的方法吗?     解答:要达到快速的更新,我们可以解法5,使用映射二分堆,可以使更新的操作达到O(logn)

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

      提示:归并排序?如果每台机器都返回最相关的K个文档,那么所有机器上最相关K个文档的并集肯定包含全集中最相关的K个文档。由于边界情况并不需要非常精确,如果每台机器返回最好的K’个文档,那么K’应该如何取值,以达到我们返回最相关的90%*K个文档是完全精确的,或者最终返回的最相关的K个文档精确度超过90%(最相关的K个文档中90%以上在全集中相关性的确排在前K),或者最终返回的最相关的K个文档最差的相关性排序没有超出110%*K。       解答:正如提示中所说,可以让每台机器返回最相关的K'个文档,然后利用归并排序的思想,得到所有文档中最相关的K个。 最好的情况是这K个文档在所有机器中平均分布,这时每台机器只要K' = K / n (n为所有机器总数);最坏情况,所有最相关的K个文档只出现在其中的某一台机器上,这时K'需近似等于K了。我觉得比较好的做法可以在每台机器上维护一个堆,然后对堆顶元素实行归并排序。

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

LeetCode:5_Longest Palindromic Substring | 最长的回文子串 | Medium

题目: Given a string S, find the longest palindromic substring in S. You may assum...

234100
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

11610
来自专栏Fish

CCF 画图

问题描述   用 ASCII 字符来画图是一件有趣的事情,并形成了一门被称为 ASCII Art 的艺术。例如,下图是用 ASCII 字符画出来的 CSPR...

25460
来自专栏数据结构与算法

深海中的STL—nth_element

如果让你求区间第k大,你会怎么做呢? 主席树?确实是个不错的选择(不过像我这种垃圾还是乖乖打暴力吧) 在c++的stl库中,提供了nth_element...

38970
来自专栏我是攻城师

使用位运算替代模运算

35250
来自专栏chenjx85的技术专栏

leetcode-55-跳跃游戏

1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

5310
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

10810
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

37370
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

349110
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

35790

扫码关注云+社区

领取腾讯云代金券