亲宝软件园·资讯

展开

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

人气:0
想了解深入第K大数问题以及算法概要的详解的相关内容吗,在本文为您仔细讲解大数算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:大数算法,下面大家一起来学习吧。

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

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

解法3: 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:
1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)

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

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

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

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

 

加载全部内容

相关教程
猜你喜欢
用户评论