http://blog.csdn.net/insistgogo/article/details/7689297
http://blog.csdn.net/v_july_v/article/details/6370650
题目描述:输入n个整数,输出其中最大的k个。
举例:输入序列1、2、3、4、5、6、7、8,输出最大的4个数字为5、6、7、8。
方法三:不对前K个数进行排序 + 不对N-k个数排序,可以使用
思路:寻找第K个大元素。
具体方法:使用类似快速排序,执行一次快速排序后,每次只选择一部分继续执行快速排序,直到找到第K个大元素为止,此时这个元素在数组位置后面的元素即所求
- 在数组S中^^随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。
- 这时有两种情况:
- 1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
- 2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。
方法七、我们要尽可能少的遍历所有数据。相比下,属于较好的算法,提倡使用
思路:维护一个大小为k的小根堆,堆顶元素是最大K 个数中最小的一个,即第K个元素
- 处理过程对于数组中的每一个元素X,判断与堆顶的大小
- 如果X 比堆顶小,则不需要改变原来的堆
- 因为这个元素比最大的K 个 数小。
- 如果X比堆顶大,要用X 替换堆顶的元素Y 。
- 调整堆的时间复杂度为O(log2K)。
时间复杂度: O (N * log2 K ),算法只需要扫描所有的数据一次
空间复杂度:大小为K的数组,只需要存储一个容量为K 的堆。
注意、大多数情况下,堆可以全部载入内存。如果K 仍然很大,我们可以尝试先找最大的K ’个元素,然后找第K ’+1个到第2 * K ’
元素,如此类推(其中容量K ’的堆可以完全载入内存)。这时,每求出K’个数,就遍历一遍数据了
方法八、可以直接对原数组建立大根堆,取这个优先队列前k个值。数据量小的时候可以考虑
思路:在线性时间内,能将一个无序的数组建成一个最小堆,然后取堆中的前k个数
建堆时间是O(n),每次调整时间为O(log n)
复杂度O(n)+k*O(log n)
在有优化,每次调整时不需要调整logn次了,只需调整K次,这个k 和 取第k个数是同一个数
也就是,建堆后,直接取出第一个最大值。取第一个最大值后,大根堆已经被破坏了,之后需要向下进行k次调整就好。取第2个最大值后,之后进行k-1次调整,等等。注意,每次取完值后,这个堆就不是大根堆了
原来堆的方法,每次调整l最大是logn次,调整后仍是大根堆
优化后的时间复杂度是O(n+k^2)
评价:这两个方法的时间复杂度都比维护一个大小为k的小根堆的方法好,但是后者是空间复杂度还是很好的,内存中只需维护一个大小为k堆,而其他两个方法需要把整个堆都放入内存,这对于处理海量数据效率还是不是很好啊,而且作者July还在程序验证过,其实这两种算法在时间上区别不是很大。
思路1:寻找第K个大的元素 + 计数排序 + 数组实现
具体方法:使用计数排序,另开辟一个数组,记录每个整数出现的次数,然后再从大到小取最大的 K 个。
缺点:
1、有些数没有出现过,仍要为其保留一个空间,空间浪费比较严重
2、不能处理浮点数
思路2:寻找第K个大的元素 + 计数排序 + map实现
具体方法:利用STL最后的map保存每一个元素Si出现的次数,之后从大到小扫描找到K个数
时间复杂度O(n*logn) 空间复杂度O(n)
注意:
1、可以处理浮点数
方法五、基数排序,不提倡使用
思路:寻找第K个大的元素 + 基数排序
时间复杂度:O ( (N +M )* log2 M (|V max - V min |/delta) )- 一次遍历,找到最大的数为Vmax ,最小的数为Vmin
- 对区间[V min , V max ]分成M 块
- 每个小区间的跨度为d =(V max – V min )/M
- 即 [V min , V min +d ], [V min + d , V min + 2d ],……
- 扫描一遍所有元素,统计各个小区间中的元素个数,我们可以知道第K大的元素在哪一个小区间。
- 然后,再对那个小区间,继续进行分块 处理。
- 。。。。递归下去,一直找到一个区间只含第K个数为止
方法六、类二分查找,不提倡使用
思路:寻找第K个大的元素 + 类二分查找
1、delta的取值要比任意两个不相等的元素差值之最小值小。如果所有元素都是整数,delta可以取值0.5。
2、算法的时间复杂度O( N * log2 (|Vmax - Vmin| /delta) )
- while(Vmax – Vmin > delta)
- {
- Vmid = Vmin + (Vmax - Vmin) * 0.5;
- if(f(arr,N,Vmid) >= K)
- Vmin = Vmid;
- else
- Vmax = Vmid;
- }
- 伪码中f(arr ,N,Vmid)返回数组arr [0, …, N-1]中大于等于Vmid的数的个数。
方法一:对所有元素进行排序,之后取出前K个元素,不提倡使用
思路:使用最快排序算法,选择快排 或 堆排
时间复杂度:O(n*logn) + O(K) = O(n*logn)
特点:需要对全部元素进行排序,K = 1 时,时间复杂度也为O(n*logn)
方法二:只需要对前K个元素排序,不需要对N-K个元素进行排序,不提倡使用
思路:使用 选择排序 或 起泡排序,进行K次选择,可得到第k大的数时间复杂度:O(n*k)
http://blog.csdn.net/v_july_v/article/details/6370650