寻找最大的k个数 - 编程之美2.5

http://blog.csdn.net/insistgogo/article/details/7689297

题目描述：输入n个整数，输出其中最大的k个。

举例：输入序列1、2、3、4、5、6、7、8，输出最大的4个数字为5、6、7、8。

方法三：不对前K个数进行排序 + 不对N-k个数排序，可以使用

思路：寻找第K个大元素。

具体方法：使用类似快速排序，执行一次快速排序后，每次只选择一部分继续执行快速排序，直到找到第K个大元素为止，此时这个元素在数组位置后面的元素即所求

1. 在数组S中^^随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。  
2. 这时有两种情况：  
3.     1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；  
4.     2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。

方法七、我们要尽可能少的遍历所有数据。相比下，属于较好的算法，提倡使用

思路：维护一个大小为k的小根堆，堆顶元素是最大K 个数中最小的一个，即第K个元素

1. 处理过程对于数组中的每一个元素X，判断与堆顶的大小  
2.     如果X 比堆顶小，则不需要改变原来的堆  
3.         因为这个元素比最大的K 个 数小。  
4.     如果X比堆顶大，要用X 替换堆顶的元素Y 。  
5.         调整堆的时间复杂度为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) )

1. 一次遍历，找到最大的数为Vmax ，最小的数为Vmin  
2. 对区间[V min , V max ]分成M 块  
3.     每个小区间的跨度为d =（V max – V min ）/M   
4.     即 [V min , V min +d ], [V min + d , V min + 2d ],……   
5. 扫描一遍所有元素，统计各个小区间中的元素个数,我们可以知道第K大的元素在哪一个小区间。  
6. 然后，再对那个小区间，继续进行分块 处理。  
7. 。。。。递归下去，一直找到一个区间只含第K个数为止  

方法六、类二分查找，不提倡使用

思路：寻找第K个大的元素 + 类二分查找

1、delta的取值要比任意两个不相等的元素差值之最小值小。如果所有元素都是整数，delta可以取值0.5。

2、算法的时间复杂度O( N * log2 (|Vmax - Vmin| /delta) ) 

1. while(Vmax – Vmin > delta)  
2. {  
3.     Vmid = Vmin + (Vmax - Vmin) * 0.5;  
4.     if(f(arr,N,Vmid) >= K)  
5.         Vmin = Vmid;  
6.     else  
7.         Vmax = Vmid;  
8. }  
9. 伪码中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